Primas Concatenadas

26

Reto:

Se le da una cadena que contiene solo dígitos. Su tarea es generar el número mínimo de primos que se deben concatenar para formar la cadena. Si esto es imposible, salida 0.

Casos de prueba:

Entrada -> Salida:

252 -> 3
235 -> 2
92 -> 0
31149 -> 2
poi830
fuente
1
Relacionado
Alex A.
¿Puede haber ceros a la izquierda?
Zgarb
Sí, puede haber ceros a la izquierda.
poi830
¿Podemos tomar una lista de dígitos?
LegionMammal978
1
¿Qué sucede si hay ceros a la izquierda?
Dennis

Respuestas:

6

JavaScript (ES6), 123 121 120 bytes

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

¡Ahorré un byte gracias a @Neil!

Explicación

Toma una sola cadena como entrada. Debido al método de verificación principal (división de prueba recursiva), el mayor número que se puede verificar con seguridad es 13840. Algunos números por encima de esto fallarán debido a que se excedió el tamaño máximo de la pila de llamadas. Sin embargo, termina instantáneamente para cada caso que pueda manejar.

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

usuario81655
fuente
¿Soy yo o se puede cambiar i?(a=...)&&(b=...)&&a+b:0a i&&(a=...)&&(b=...)&&a+b?
Neil
5

MATL , 26 24 bytes

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

Toma algunos segundos para algunos de los casos de prueba.

Pruébalo en línea!

Explicación

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
fuente
4

Pyth - 19 17 16 bytes

lhf.AmP_sdTa./zY

Test Suite .

Maltysen
fuente
En su forma más reciente, este cuenta 0 y 1 como primos. Sin embargo, antes de la edición, no lo hizo.
poi830
1
@ poi830 lo arregló.
Maltysen
2

Bash + Coreutils 169 158 149 bytes

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

Contamos en unario, generando una línea con una bpara cada primo y una terminando aal final de la línea (para que printftenga un token con el que trabajar).

La prueba de primalidad es factor $n | grep -q ': \w*$', que determina si el número tiene exactamente un factor primo.

Particionamos recursivamente la entrada; Si la mitad izquierda es primo, filtramos los resultados de la mitad derecha agregando uno a cada valor. La devolución ade una entrada de longitud cero finaliza la recursión.

Finalmente, tomamos todos los resultados y los clasificamos para encontrar el más corto (ignorando cualquiera que no tenga el valor ade indicar éxito); debemos eliminar dos (para el insertado ay para la nueva línea), luego contar los caracteres para dar el resultado.

Pruebas

$ 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

Agregué 111a las pruebas para mostrar que 1se considera correctamente no primo.

Toby Speight
fuente
Iba a sugerir esto . La mayoría de mis modificaciones son probablemente obsoletas ahora, pero otras deberían funcionar.
Dennis
@Dennis: me gusta cgenerar la final 0. Sin embargo, no estoy tan interesado en el copioso stderr. Si lo desea, puede usar (versiones de) mi respuesta como base para la suya propia.
Toby Speight
2

Mathematica, 142 135 bytes

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

Como puede ver, Mathematica no fue creado para esta tarea. Toma una lista de dígitos.

LegionMammal978
fuente
¿Se puede usar en And@@lugar de AllTrue? Debe guardar 4-5 bytes.
CalculatorFeline
Flatten[#,1]=Join@@@#
CalculatorFeline
Um ... da error y respuesta incorrecta en 133 ... usaste todos los casos de prueba, ¿verdad?
CalculatorFeline
@CatsAreFluffy Golfó y aclaró.
LegionMammal978