Dado un número entero n
, devuelve el número de formas en que n se puede escribir como una lista de números primos. Por ejemplo, 2323
se puede escribir como (2,3,23)
, (23,23)
o (2,3,2,3)
o (23,2,3)
, para que salga 4
. Si no se puede escribir de esta manera, debe generar 0
.
Un número primo como 019
o 00000037
es un primo válido para este problema.
Casos de prueba:
5 -> 1
55 -> 1
3593 -> 4 (359 and 3, or 3 and 593, or 3 and 59 and 3, or 3593)
3079 -> 2 (3 and 079, or 3079)
119 -> 0
5730000037 -> 7 (5,7,3,000003,7, 5,7,3,0000037, 5,73,000003,7, 5,73,0000037, 5,73000003,7, 5,7,30000037, 5730000037)
0-> undefined (you do not have to handle this case)
Este es el código de golf , por lo que gana la respuesta más corta en bytes en cada idioma.
Editar: ahora sé por qué debería usar el sandbox la próxima vez
code-golf
math
primes
set-partitions
equipado
fuente
fuente
Respuestas:
Haskell ,
9689 bytes5 bytes guardados gracias a la prueba de primalidad de H.PWiz
Pruébalo en línea!
Explicación
Lo primero que se hace es crear una función de prueba principal
usando el teorema de Wilsonusando la definición de prima.Entonces comience a definir
f
. Lo primero que pensé cuando vi este problema fue usar programación dinámica. Sin embargo, la programación dinámica cuesta bytes, por lo que utiliza un algoritmo de "programación psuedo-dinámica". Mientras que en la programación dinámica, almacenaría un gráfico Acíclico Dirigido en la memoria aquí, solo usamos recursividad y recalculamos cada nodo cada vez que lo necesitamos. Pierde todo el tiempo los beneficios de la programación dinámica, pero este es el código de golf, así que a quién le importa. (Aún mejor que la búsqueda de fuerza bruta)El algoritmo es el siguiente, construimos un gráfico acíclico dirigido, L , donde cada nodo representa una subcadena del número. En particular, L i representa los últimos dígitos i de nuestra entrada (llamémosla n ).
Definimos que L 0 tiene un valor de 1 y el valor de cada uno en L para tener la suma de cada L j de manera que j <i y la subcadena de n de i a j es primo.
O en una fórmula:
Entonces volvemos al valor en el índice más grande más grande de L . ( L k donde k es el número de dígitos de n )
fuente
Jalea , 8 bytes
Pruébalo en línea!
-1 byte gracias a Leaky Nun
-1 byte gracias a Dennis
Explicación
fuente
Brachylog , 10 bytes
Pruébalo en línea!
Primero
ṫ
convierte la entrada en una cadena.{…}ᶜ
Cuenta el número de posibles salidas para…
.Dentro de
{…}
la salida deṫ
se alimenta a~c
. La salida de este predicado satisface que, cuando se concatena, es igual a la entrada. Esto se alimentaịᵐ
, lo que especifica que su salida es su entrada con cada cadena convertida en un entero.ṗᵐ
especifica que su entrada consiste en primosfuente
{~cṗᵐ}ᶜ
. Esto es realmente lento porque~c
en los enteros funciona con aritmética de restricción, pero en teoría funciona.Pyth , 13 bytes
Banco de pruebas.
fuente
Python 2 ,
1059591 bytesEsto es muy lento
Pruébalo en línea!
fuente
Python 2 , 161 bytes
Pruébalo en línea!
La función
g
crea las particiones de forma recursiva (toma una cadena como entrada pero genera una lista de listas de entradas). La mayor parte del código restante es solo para implementar '¿esd
primo?'.fuente
Gaia , 12 bytes
Pruébalo en línea!
fuente
Limpias ,
199141131 bytesPruébalo en línea!
fuente
J ,
6564 bytesPruébalo en línea!
fuente
Pyth, 12 bytes
Toma la entrada como un entero, salidas
True
oFalse
Pruébalo en línea!
fuente