Primat penggabungan

26

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
poi830
sumber
1
Terkait
Alex A.
Bisakah ada angka nol di depan?
Zgarb
Ya, bisa ada nol di depan.
poi830
Bisakah kita mengambil daftar angka?
LegionMammal978
1
Apa yang terjadi jika ada angka nol di depan?
Dennis

Jawaban:

6

JavaScript (ES6), 123 121 120 byte

f=(s,v)=>(p=n=>--n-1?s%n&&p(n):1)(s)||[...s].map((_,i)=>!(n=i&&(a=f(s.slice(0,i)))&&(b=f(s.slice(i)))&&a+b)|n>v?0:v=n)|v

Menyimpan 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.

f=(s,v)=>
  (p=n=>--n-1?s%n&&p(n):1)(s) // if s is prime, return 1
  ||[...s].map((_,i)=>        // else for each index in s, split s into 2
    !(n=i&&                   // v = return value (initialised to undefined)
      (a=f(s.slice(0,i)))&&
      (b=f(s.slice(i)))&&
      a+b
    )|n>v?0:v=n               // if i, a, b and n are all > 0 and !(n > v), v = n
  )|v                         // cast v to an integer and return it

// Test
var testCases = [ "252", "235", "92", "3149", "24747" ];
document.write("<pre>" + testCases.map(c => c + ": " + f(c)).join("\n"));

pengguna81655
sumber
Apakah saya atau dapat Anda mengubah i?(a=...)&&(b=...)&&a+b:0ke i&&(a=...)&&(b=...)&&a+b?
Neil
5

MATL , 26 24 byte

0in:"GUtZq@Z^V10ZA=a?x@.

Diperlukan beberapa detik untuk beberapa kasus uji.

Cobalah online!

Penjelasan

0       % Push 0
in:     % Take input. Generate array [1,2,...,N] where N is input length
"       % For each. In each iteration the number of used primes is increased
  GU    %   Push input. Convert to number
  tZq   %   Duplicate. Array of primes smaller than the input
  @     %   Push number of primes to bes tested in this iteration
  Z^    %   Cartesian power
  V     %   Convert to 2D array. Each row is a combination of primes
  10ZA  %   Convert each row to base 10, disregarding spaces
  =a    %   Do any of the results equal the input number? 
  ?     %   If so
    x   %     Remove the 0 that's at the bottom of the stack
    .   %     Break for each loop
        %   Implicitly end if
        % Implicitly end for each
        % Implicitly display
Luis Mendo
sumber
4

Pyth, 16 byte

lhaf!f!P_sYT./zY

Suite uji

Penjelasan untuk diikuti.

isaacg
sumber
4

Pyth - 19 17 16 byte

lhf.AmP_sdTa./zY

Test Suite .

Maltysen
sumber
Dalam bentuk yang lebih baru, yang ini dihitung 0 dan 1 sebagai bilangan prima. Namun, sebelum diedit, ternyata tidak.
poi830
1
@ poi830 memperbaikinya.
Maltysen
2

Bash + coreutils, 169 158 149 byte

c()
{
test $1||echo a
for i in `seq ${#1}`
do factor ${1::$i}|grep -q ': \w*$'&&printf b%s\\n `c ${1:$i}`
done
}
c $1|sort|sed '/a/!d;s/..//;q'|wc -c

Kami menghitung secara unary, menghasilkan garis dengan satu buntuk setiap prime dan berakhir apada 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. Kembalia 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

$ for i in 252 235 92 31149 111; do echo "$i:"$'\t'"$(./77623.sh $i)"; done
252:    3
235:    2
92:     0
31149:  2
111:    0

Saya menambahkan 111ke tes untuk menunjukkan yang 1benar dianggap non-prime.

Toby Speight
sumber
Saya akan menyarankan ini . Sebagian besar modifikasi saya mungkin sudah usang sekarang, tetapi yang lain masih berfungsi.
Dennis
@ Dennis - Saya suka cuntuk menghasilkan final 0. Namun, tidak begitu tertarik pada stderr yang berlebihan. Anda boleh menggunakan (versi) jawaban saya sebagai dasar untuk jawaban Anda sendiri jika Anda mau.
Toby Speight
2

Mathematica, 142 135 byte

Min[Length/@Select[Join@@@Permutations/@IntegerPartitions@Length[a=#],And@@PrimeQ@*FromDigits/@a~Internal`PartitionRagged~#&]]/.∞->0&

Seperti yang Anda lihat, Mathematica tidak dibuat untuk tugas ini. Mengambil daftar digit.

LegionMammal978
sumber
Bisakah Anda menggunakan And@@bukan AllTrue? Harus menyimpan 4-5 byte.
CalculatorFeline
Flatten[#,1]=Join@@@#
CalculatorFeline
Um ... memberikan jawaban salah dan salah pada 133 ... Anda memang menggunakan semua test case, kan?
CalculatorFeline
@CatsAreFluffy Bermain Golf dan klarifikasi.
LegionMammal978