Wyzwanie:

Otrzymujesz ciąg zawierający tylko cyfry. Twoim zadaniem jest wyprowadzenie minimalnej liczby liczb pierwszych, które muszą zostać połączone w celu utworzenia łańcucha. Jeśli jest to niemożliwe, wyjdź 0.

Przypadki testowe:

Wejście -> Wyjście:

252 -> 3
235 -> 2
92 -> 0
31149 -> 2

JavaScript (ES6), 123 121 120 bajtów

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

Zapisano bajt dzięki @Neil!

Wyjaśnienie

Pobiera jeden ciąg jako dane wejściowe. Ze względu na metodę sprawdzania pierwotnego (podział próby rekurencyjnej) największą liczbą, którą można bezpiecznie sprawdzić, jest 13840. Niektóre liczby powyżej tego nie będą działać z powodu przekroczenia maksymalnego rozmiaru stosu wywołań. Jednak kończy się natychmiast dla każdego obsługiwanego przypadku.

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"));

MATL , 26 24 bajtów

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

W przypadku niektórych przypadków testowych zajmuje to kilka sekund.

Wypróbuj online!

Wyjaśnienie

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

Pyth, 16 bajtów

lhaf!f!P_sYT./zY

Zestaw testowy

Wyjaśnienie do naśladowania.

Pyth - 19 17 16 bajtów

lhf.AmP_sdTa./zY

Pakiet testowy .

Bash + coreutils, 169 158 149 bajtów

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

Liczymy jako jedności, wypisując linię z jednym bdla każdej liczby pierwszej i zakończeniem ana końcu linii (tak, że printfma token do pracy).

Test pierwotności polega na factor $n | grep -q ': \w*$'określeniu, czy liczba ma dokładnie jeden czynnik pierwszy.

Rekurencyjnie dzielimy dane wejściowe; jeśli lewa połowa jest liczbą pierwszą, filtrujemy wyniki prawej połowy, dodając po jednej do każdej wartości. Zwrócenie adanych wejściowych o zerowej długości przerywa rekurencję.

Na koniec bierzemy wszystkie wyniki i sortujemy, aby znaleźć najkrótszy (ignorując te, które nie muszą aoznaczać sukcesu); musimy usunąć dwa (dla wstawionego ai dla nowego wiersza), a następnie policzyć znaki, aby dać wynik.

Testy

$ 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

Dodałem 111do testów, aby pokazać, że 1jest poprawnie uważany za niepierwszy.

Mathematica, 142 135 bajtów

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

Jak widać, Mathematica nie została stworzona do tego zadania. Pobiera listę cyfr.