Défi:

Vous obtenez une chaîne contenant uniquement des chiffres. Votre tâche consiste à afficher le nombre minimum de nombres premiers qui doivent être concaténés pour former la chaîne. Si cela est impossible, sortez 0.

Cas de test:

Entrée -> Sortie:

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

JavaScript (ES6), 123 121 120 octets

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

Un octet enregistré grâce à @Neil!

Explication

Prend une seule chaîne en entrée. En raison de la méthode de vérification principale (division d'essai récursive), le plus grand nombre pouvant être vérifié en toute sécurité est 13840. Certains nombres au-dessus de cela échoueront en raison du dépassement de la taille maximale de la pile d'appels. Cependant, il se termine instantanément pour chaque cas qu'il peut gérer.

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 octets

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

Cela prend quelques secondes pour certains des cas de test.

Essayez-le en ligne!

Explication

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 octets

lhaf!f!P_sYT./zY

Suite de tests

Explication à suivre.

Pyth - 19 17 16 octets

lhf.AmP_sdTa./zY

Suite de tests .

Bash + coreutils, 169 158 149 octets

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

Nous comptons en unaire, produisant une ligne avec un bpour chaque nombre premier et une terminaison aà la fin de la ligne (ce qui printfa un jeton avec lequel travailler).

Le test de primalité est factor $n | grep -q ': \w*$', qui détermine si le nombre a exactement un facteur premier.

Nous partitionnons récursivement l'entrée; si la moitié gauche est première, nous filtrons les résultats de la moitié droite en ajoutant un à chaque valeur. Le retour ad'une entrée de longueur nulle met fin à la récursivité.

Enfin, nous prenons tous les résultats et trions pour trouver le plus court (en ignorant ceux qui n'ont pas le apour indiquer le succès); il faut en supprimer deux (pour l'inséré aet pour la nouvelle ligne), puis compter les caractères pour donner le résultat.

Les tests

$ 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

J'ai ajouté 111aux tests pour montrer qu'il 1est correctement considéré comme non premier.

Mathematica, 142 135 octets

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

Comme vous pouvez le voir, Mathematica n'a pas été conçu pour cette tâche. Prend une liste de chiffres.