Podając liczbę całkowitą n, zwróć liczbę sposobów, w których n można zapisać jako listę liczb pierwszych. Na przykład 2323można zapisać jako (2,3,23), (23,23)lub (2,3,2,3)lub (23,2,3), aby uzyskać dane wyjściowe 4. Jeśli nie można tego zapisać w ten sposób, powinieneś wydrukować 0.

Liczba pierwsza, taka jak 019lub, 00000037jest poprawną liczbą pierwszą dla tego problemu.

Przypadki testowe:

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)

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach w każdym języku!

Edycja: teraz wiem, dlaczego następnym razem powinienem użyć piaskownicy

Haskell , 96 89 bajtów

5 bajtów zapisanych dzięki testowi pierwszeństwa 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]

Wypróbuj online!

Wyjaśnienie

Pierwszą rzeczą, która jest zrobiona, jest utworzenie pierwszej funkcji testowej przy użyciu twierdzenia Wilsona przy użyciu definicji liczby pierwszej.

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

Następnie zacznij definiować f. Pierwszą rzeczą, o której pomyślałem, kiedy zobaczyłem ten problem, było użycie programowania dynamicznego. Jednak programowanie dynamiczne kosztuje bajty, więc wykorzystuje to algorytm „programowania dynamicznego psuedo”. Podczas gdy w programowaniu dynamicznym zapisujesz tutaj w pamięci wykres Directed Acyclic, po prostu używamy rekurencji i ponownie obliczamy każdy węzeł za każdym razem, gdy go potrzebujemy. Traci cały czas korzyści z programowania dynamicznego, ale jest to golf golfowy więc kogo to obchodzi. (wciąż lepsze niż wyszukiwanie brutalną siłą)

Algorytm wygląda następująco: tworzymy Directed Acyclic Graph, L , gdzie każdy węzeł reprezentuje podłańcuch liczby. W szczególności L _i reprezentuje ostatnie i cyfry naszego wejścia (nazwijmy to n ).

Zdefiniować L ₀ ma wartość 1, a każdy z inną wartość L mają sumę poszczególnych L _j, tak, że j <i a podłańcuchem n od I do j jest liczbą pierwszą.

Lub we wzorze:

Następnie zwraca wartość w najszerszym największy wskaźnik L . ( L _k gdzie k jest liczbą cyfr n )

Galaretka , 8 bajtów

ŒṖḌÆPẠ€S

Wypróbuj online!

-1 bajt dzięki Leaky Nun
-1 bajt dzięki Dennis

Wyjaśnienie

ŒṖḌÆ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

Brachylog , 10 bajtów

ṫ{~cịᵐṗᵐ}ᶜ

Wypróbuj online!

Najpierw ṫkonwertuje dane wejściowe na ciąg. {…}ᶜLiczy liczbę możliwych wyników dla ….

Wewnątrz {…}wyjście ṫjest podawane do ~c. Wyjście tego predykatu spełnia to, że po połączeniu jest równe wkładowi. Jest podawany do ịᵐ, co określa, że ​​jego wyjściem jest wejście z każdym łańcuchem przekonwertowanym na liczbę całkowitą. ṗᵐokreśla, że ​​jego dane wejściowe składają się z liczb pierwszych

Pyth , 13 bajtów

lf.AmP_sdT./`

Zestaw testowy.

Python 2 , 105 95 91 bajtów

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)

To jest bardzo wolne.

Wypróbuj online!

Python 2 , 161 bajtów

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)]]

Wypróbuj online!

Funkcja gtworzy rekurencyjnie partycje (pobiera ciąg jako dane wejściowe, ale wyświetla listę list liczb całkowitych). Większość pozostałego kodu to tylko implementacja „czy liczba dpierwsza?”.

Gaia , 12 bajtów

₸B¦ṗ¦Π
$ḍ↑¦Σ

Wypróbuj online!

Czysty , 199 141 131 bajtów

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]

Wypróbuj online!

J , 65 64 bajtów

(1#.[:*/"1*/@>)@(#`(1,.[:#:[:i.2^#-1:)@.(1<#)(1:p:&.>".);.1])@":

Wypróbuj online!

Pyth, 12 bajtów

lf*FmP_sdT./    

Pobiera dane wejściowe jako liczbę całkowitą, wyjścia TruelubFalse

Wypróbuj online!