Descomponiéndose en primos

14

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, 2323se 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 019o 00000037es 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 , 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

equipado
fuente
Relacionado
Peter Taylor

Respuestas:

7

Haskell , 96 89 bytes

5 bytes guardados gracias a la prueba de primalidad de H.PWiz

p x=[1|0<-mod x<$>[2..x]]==[1]
f[]=1
f b=sum[f$drop i b|i<-[1..length b],p$read$take i b]

Pruébalo en línea!

Explicación

Lo primero que se hace es crear una función de prueba principal usando el teorema de Wilson usando la definición de prima.

p x=[1|0<-mod x<$>[2..x]]==[1]

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 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:

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 )

Post Rock Garf Hunter
fuente
6

Jalea , 8 bytes

ŒṖḌÆPẠ€S

Pruébalo en línea!

-1 byte gracias a Leaky Nun
-1 byte gracias a Dennis

Explicación

ŒṖḌÆPẠ€S  Main Link
ŒṖ        List Partitions (automatically converts number to decimal digits)
  Ḍ       Convert back to integers (auto-vectorization)
   ÆP     Are they primes? (auto-vectorization)
     Ạ€   For each, are they all truthy (were the numbers all primes?); 1/0 for truthy/falsy
       S  Sum; gets number of truthy elements
Hiperneutrino
fuente
Me di cuenta de que 05AB1E no puede hacer esto fácilmente. Las particiones parecen un gran comando.
Urna mágica del pulpo
5

Brachylog , 10 bytes

ṫ{~cịᵐṗᵐ}ᶜ

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 primos

H.PWiz
fuente
1
No es necesario para convertir a la cadena y la espalda, los 7 bytes son suficientes: {~cṗᵐ}ᶜ. Esto es realmente lento porque ~cen los enteros funciona con aritmética de restricción, pero en teoría funciona.
Fatalize
@Fatalize Creo que no tiene en cuenta los ceros a la izquierda
H.PWiz
4

Pyth , 13 bytes

lf.AmP_sdT./`

Banco de pruebas.

Monja permeable
fuente
No conozco a Pyth tan bien, pero en lugar de filtrar y luego tomar la longitud, ¿podría hacer for_each en lugar de filtrar y luego sumar?
HyperNeutrino
@HyperNeutrino, ¿eso hace alguna diferencia?
Leaky Nun
No estoy seguro, no lo he probado. Lo hace para Jelly (probablemente debido al filtro rápido de dos bytes) pero no estoy seguro.
HyperNeutrino
@HyperNeutrino filtro es un byte aquí ...
Leaky Nun
3

Python 2 , 105 95 91 bytes

f=lambda n:sum(0**k|f(n%10**k)for k in range(n)if sum(n/10**k%j<1for j in range(1,n+2))==2)

Esto es muy lento

Pruébalo en línea!

Dennis
fuente
2

Python 2 , 161 bytes

lambda n:sum(all(d>1and all(d%i>0for i in range(2,d))for d in v)for v in g(`n`))
g=lambda s:[[int(s[:i])]+t for i in range(1,len(s))for t in g(s[i:])]+[[int(s)]]

Pruébalo en línea!

La función gcrea 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 '¿es dprimo?'.

Chas Brown
fuente
1

Limpias , 199 141 131 bytes

import StdEnv
?n|n<2=0|and[gcd n i<2\\i<-[2..n-1]]=1=0
@n#s=toString n
#f=toInt o(%)s
= ?n+sum[@(f(0,i))\\i<-[0..n]| ?(f(i+1,n))>0]

Pruébalo en línea!

Οurous
fuente