In Primzahlen zerlegen

14

Geben Sie bei einer Ganzzahl ndie Anzahl der Möglichkeiten zurück, mit denen n als Liste von Primzahlen geschrieben werden kann. Zum Beispiel 2323kann geschrieben werden (2,3,23), (23,23)oder (2,3,2,3)oder (23,2,3), so würden Sie Ausgang4 . Wenn es nicht auf diese Weise geschrieben werden kann, sollten Sie ausgeben0 .

Eine Primzahl wie 019oder00000037 ist eine gültige Primzahl für dieses Problem.

Testfälle:

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)

Das ist , also gewinnt die kürzeste Antwort in Bytes in jeder Sprache!

Edit: Jetzt weiß ich, warum ich das nächste Mal die Sandbox benutzen soll

manipulierten
quelle
Related
Peter Taylor

Antworten:

7

Haskell , 96 89 Bytes

5 Bytes gespart dank H.PWiz's Primalitätstest

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]

Probieren Sie es online!

Erläuterung

Das erste, was getan wird, ist die Erstellung einer Primzahl-Testfunktion unter Verwendung des Wilson-Theorems unter Verwendung der Definition von Primzahl.

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

Beginnen Sie dann mit der Definition f. Das erste, was ich dachte, als ich dieses Problem sah, war die dynamische Programmierung. Die dynamische Programmierung kostet jedoch Byte, sodass ein Algorithmus für die "pseudodynamische Programmierung" verwendet wird. Während Sie in der dynamischen Programmierung einen gerichteten azyklischen Graphen im Speicher ablegen würden, verwenden wir hier nur die Rekursion und berechnen jeden Knoten jedes Mal neu, wenn wir ihn benötigen. Es verliert alle Zeitvorteile der dynamischen Programmierung, aber das ist , wen interessiert das? (Immer noch besser als Brute-Force-Suche)

Der Algorithmus lautet wie folgt: Wir konstruieren einen gerichteten azyklischen Graphen L , wobei jeder Knoten eine Teilzeichenfolge der Zahl darstellt. Insbesondere repräsentiert L i die letzten i Ziffern unserer Eingabe (nennen wir es n ).

Wir definieren L 0 , um einen Wert von 1 zu haben, und jeden anderen Wert in L , um die Summe von jedem L j zu haben, so dass j <i und der Teilstring von n von i bis j eine Primzahl ist.

Oder in einer Formel:

Formel

Wir geben dann den Wert am größten größten Index von L zurück . ( L k wobei k die Anzahl der Stellen von n ist )

Post Rock Garf Hunter
quelle
6

Gelee , 8 Bytes

ŒṖḌÆPẠ€S

Probieren Sie es online!

-1 Byte dank Leaky Nun
-1 Byte dank Dennis

Erläuterung

ŒṖḌÆ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
HyperNeutrino
quelle
Mir ist aufgefallen, dass 05AB1E dies nicht einfach kann. Partitionen scheinen ein großer Befehl zu sein.
Magic Octopus Urn
5

Brachylog , 10 Bytes

ṫ{~cịᵐṗᵐ}ᶜ

Probieren Sie es online!

Zuerst konvertiert die Eingabe in eine Zeichenfolge. {…}ᶜZählt die Anzahl der möglichen Ausgänge für .

Im Inneren wird {…}der Ausgang von zugeführt ~c. Die Ausgabe dieses Prädikats entspricht in der Verkettung der Eingabe. Dies wird ịᵐeingegeben, was angibt, dass es sich bei der Ausgabe um die Eingabe handelt, wobei jeder String in eine Ganzzahl konvertiert wird. ṗᵐGibt an, dass die Eingabe aus Primzahlen besteht

H.PWiz
quelle
1
Sie müssen nicht zu konvertieren String und zurück benötigt, sind die 7 Byte genug: {~cṗᵐ}ᶜ. Dies ist sehr langsam, da ~cbei ganzen Zahlen mit Constraint-Arithmetik gearbeitet wird, aber theoretisch funktioniert es.
Fatalize
@ Fatalize Ich denke, dass führende Nullen nicht berücksichtigt werden
H.PWiz
4

Pyth , 13 Bytes

lf.AmP_sdT./`

Testsuite.

Undichte Nonne
quelle
Ich kenne Pyth nicht so gut, aber anstatt zu filtern und dann die Länge zu nehmen, könntest du for_each tun, anstatt zu filtern und dann zu summieren?
HyperNeutrino
@HyperNeutrino macht das einen Unterschied?
Undichte Nonne
Ich bin nicht sicher, ich habe nicht getestet. Das tut es für Jelly (wahrscheinlich wegen des Zwei-Byte-Filters schnell), aber ich bin mir nicht sicher.
HyperNeutrino
@HyperNeutrino Filter ist ein Byte hier ...
Undichte Nonne
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)]]

Probieren Sie es online!

Die Funktion gerstellt die Partitionen rekursiv (es wird eine Zeichenfolge als Eingabe verwendet, es wird jedoch eine Liste mit Ints-Listen ausgegeben). Der größte Teil des verbleibenden Codes besteht lediglich aus der Implementierung von 'is da prime?'.

Chas Brown
quelle
1

Sauber , 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]

Probieren Sie es online!

Οurous
quelle
0

Pyth, 12 Bytes

lf*FmP_sdT./    

Übernimmt Eingaben als Ganzzahl, gibt Trueoder ausFalse

Probieren Sie es online!

Dave
quelle