Tantangan:
Anda diberi string yang hanya berisi digit. Tugas Anda adalah menampilkan jumlah minimum bilangan prima yang harus disatukan untuk membentuk string. Jika ini tidak mungkin, hasilkan 0
.
Kasus uji:
Input -> Output:
252 -> 3
235 -> 2
92 -> 0
31149 -> 2
Jawaban:
JavaScript (ES6),
123121120 byteMenyimpan satu byte berkat @Neil!
Penjelasan
Mengambil string tunggal sebagai input. Karena metode pemeriksaan utama (divisi uji rekursif), jumlah terbesar yang dapat diperiksa dengan aman adalah
13840
. Beberapa nomor di atas ini akan gagal karena ukuran tumpukan panggilan maksimum yang terlampaui. Namun, selesai secara instan untuk setiap kasus yang dapat ditangani.sumber
i?(a=...)&&(b=...)&&a+b:0
kei&&(a=...)&&(b=...)&&a+b
?MATL ,
2624 byteDiperlukan beberapa detik untuk beberapa kasus uji.
Cobalah online!
Penjelasan
sumber
Pyth, 16 byte
Suite uji
Penjelasan untuk diikuti.
sumber
Pyth -
191716 byteTest Suite .
sumber
Bash + coreutils,
169158149 byteKami menghitung secara unary, menghasilkan garis dengan satu
b
untuk setiap prime dan berakhira
pada akhir baris (sehinggaprintf
memiliki token untuk bekerja dengan).Tes primality adalah
factor $n | grep -q ': \w*$'
, yang menentukan apakah angka tersebut memiliki tepat satu faktor utama.Kami membagi input secara rekursif; jika setengah kiri adalah prima, kami menyaring hasil dari setengah kanan dengan menambahkan satu ke setiap nilai. Kembali
a
untuk input panjang nol akan mengakhiri rekursi.Akhirnya, kami mengambil semua hasil dan mengurutkan untuk menemukan yang terpendek (mengabaikan semua yang tidak memiliki
a
indikasi keberhasilan); kita harus menghapus dua (untuk yang disisipkana
dan untuk baris baru), lalu hitung karakter untuk memberikan hasilnya.Tes
Saya menambahkan
111
ke tes untuk menunjukkan yang1
benar dianggap non-prime.sumber
c
untuk menghasilkan final0
. Namun, tidak begitu tertarik pada stderr yang berlebihan. Anda boleh menggunakan (versi) jawaban saya sebagai dasar untuk jawaban Anda sendiri jika Anda mau.Mathematica,
142135 byteSeperti yang Anda lihat, Mathematica tidak dibuat untuk tugas ini. Mengambil daftar digit.
sumber
And@@
bukanAllTrue
? Harus menyimpan 4-5 byte.Flatten[#,1]
=Join@@@#