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
Respuestas:
JavaScript (ES6),
123121120 bytes¡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.fuente
i?(a=...)&&(b=...)&&a+b:0
ai&&(a=...)&&(b=...)&&a+b
?MATL ,
2624 bytesToma algunos segundos para algunos de los casos de prueba.
Pruébalo en línea!
Explicación
fuente
Pyth, 16 bytes
Banco de pruebas
Explicación a seguir.
fuente
Pyth -
191716 bytesTest Suite .
fuente
Bash + Coreutils
169158149 bytesContamos en unario, generando una línea con una
b
para cada primo y una terminandoa
al final de la línea (para queprintf
tenga 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
a
de 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
a
de indicar éxito); debemos eliminar dos (para el insertadoa
y para la nueva línea), luego contar los caracteres para dar el resultado.Pruebas
Agregué
111
a las pruebas para mostrar que1
se considera correctamente no primo.fuente
c
generar la final0
. 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.Mathematica,
142135 bytesComo puede ver, Mathematica no fue creado para esta tarea. Toma una lista de dígitos.
fuente
And@@
lugar deAllTrue
? Debe guardar 4-5 bytes.Flatten[#,1]
=Join@@@#