Finde Primes in Pi

30

Primes sind überall ...

Sie verstecken sich in Pi

3.141592653 58979 3238 462643 3832 795028841 971693993751

Lassen Sie uns diese Primzahlen bekommen!

Die Herausforderung

Wenn Sie eine Ganzzahl als Eingabe eingeben n>0, ermitteln Sie, wie viele Primzahlen in den ersten nZiffern von verborgen sindPi

Beispiele

Denn n=3wir sollten nach Primzahlen suchen [3,1,4]. Es gibt 2 Primes (3,31), daher sollte Ihr Code ausgegeben werden. 2
Für n=10sind die ersten 10 Ziffern [3,1,4,1,5,9,2,6,5,3]und Ihr Code sollte ausgegeben werden, 12weil [2, 3, 5, 31, 41, 53, 59, 653, 4159, 14159, 314159, 1592653]sie ausgeblendet (und gefunden) wurden.

Testfälle

Eingabe -> Ausgabe

1->1  
3->2  
13->14  
22->28  
42->60  
50->93

150->197  
250->363  
500->895

Regeln

Ihr Code muss in der Lage sein , alle Primzahlen zu finden. Zumindest fürn=50
Ja, Sie können die ersten 50 Ziffern von Einträgen hartcodieren,Pi wenn Sie
möchten, sind die Antworten ungültig

Dies ist kürzeste Antwort in Bytes gewinnt!


quelle
6
msgstr "Sie können die ersten 50 Stellen von Pi fest codieren, wenn Sie möchten" . Erstes Problem gelöst! Jetzt für den Golf-Primalitätstest mit bis zu 50-stelligen Ganzzahlen ... O_o (Dies ist eine schöne Herausforderung, aber solide mathematische Einbauten oder Bibliotheken sind wahrscheinlich erforderlich.)
Arnauld
3
@totallyhuman Diese Sequenz noch nicht einmal in OEIS! Zeit für Ihren Ruhmesanspruch?
Sanchises
3
IMO, das die Hardcodierung der ersten 50 Werte ermöglicht, wirkt sich nachteilig auf diese Herausforderung aus. Diese Herausforderung besteht im Wesentlichen aus zwei Teilen: 1) Versuchen Sie, die ersten 50 Werte zu komprimieren, oder 2) Führen Sie die Herausforderung tatsächlich aus.
JAD
2
Normalerweise reicht es bei solchen Herausforderungen, bei denen die Berechnung schwieriger / langsamer / speicherintensiver wird, aus, wenn das Programm theoretisch arbeitet, anstatt einen willkürlichen Grenzwert festzulegen und die Hardcodierung zuzulassen.
JAD
3
@BillSteihn Das Aktualisieren von Regeln nach mehreren Antworten widerspricht dem Geist dieser Website. Hast du diese Frage in der Sandbox gepostet ? Sie hätten sehr früh Feedback bekommen, dass hartcodierte Antworten eingehen würden.
Olivier Grégoire

Antworten:

20

05AB1E ,  10  8 Bytes

-2 Bytes dank Adnan ( pvektorisiert)

<žsþŒÙpO

Probieren Sie es online! (Funktioniert bis zu n = 98413, ist aber auch für n = 50 sehr langsam, da so große Zahlen auf Primalität geprüft werden müssen. TIO läuft bei n = 50 nach 60 Sekunden ab.)

Wie?

<žsþŒÙpO - implicitly push input, n
<        - decrement = n-1
 žs      - pi to that many decimal places (i.e. to n digits)
   þ     - only the digits (get rid of the decimal point)
    Œ    - all sublists
     Ù   - unique values
      p  - is prime? (vectorises) 1 if so, 0 otherwise
       O - sum
         - implicitly print the top of the stack
Jonathan Allan
quelle
<žsþŒÙpOsollte für 8 Bytes arbeiten
Adnan
Ah yeah pvektorisiert danke!
Jonathan Allan
2
Ja! Endlich eine sehr kurze Code Golf Antwort, die ich wirklich verstehe! : D
Fabian Röling
11

Mathematica, 76 Bytes

Tr[1^Union@Select[FromDigits/@Subsequences@#&@@RealDigits[Pi,10,#],PrimeQ]]&
J42161217
quelle
Oh nein, fair, ich kenne Mathematica Golf nicht. : P (+1)
totalhuman
@totallyhuman Wir haben dies zur gleichen Zeit gepostet. das ist so seltsam!
J42161217
Ich habe meine Antwort mit einigen der syntaktischen Tricks bewertet, aber ich habe die Funktionen beibehalten, die ich zuvor verwendet habe. Ich hoffe es macht dir nichts aus.
Totalhuman
Tr[1^...]Das ist eine clevere Methode, um die Länge der Liste zu ermitteln, schön!
numbermaniac
6

Mathematica, 104 97 90 Bytes

Length@DeleteDuplicates@Select[FromDigits/@Subsequences@First@RealDigits[Pi,10,#],PrimeQ]&

Hahahaha, ich habe es geschafft, diese Arbeit zu machen. Ich habe keine Ahnung, wie man Mathematica benutzt. XD

Eingang:

[50]
total menschlich
quelle
1
Du hast ein paar Sekunden vor mir gepostet. und unsere antworten sind sehr ähnlich! +1
J42161217
Sind Sie sicher, welche Zahlen Sie gerade gepostet haben (überprüfen Sie die Rundung der Ziffern) ?
Jonathan Allan
@ JonathanAllan 50 96Das OP sagt, dass 50 Ziffern 93 Primzahlen enthalten, sodass Sympys Genauigkeit möglicherweise nicht stimmt.
Totalhuman
@ JonathanAllan Verwendet Sympy einen probabilistischen oder einen deterministischen Primalitätstest? (Dieselbe Frage für Mathematicas PrimeQ.)
Arnauld
@ Arnauld guter Punkt, nicht sicher.
Jonathan Allan
3

Python 3 , 274 237 207 194 189 Bytes

-37 Bytes dank Wheat Wizard! -14 Bytes dank Mr.Xcoder.

Codiert die ersten 50 Stellen von pi fest , berechnet aber alles andere manuell.

x=int(input());l="31415926535897932384626433832795028841971693993751"[:x]
print(sum(all(i%m for m in range(2,i))for i in{int(i)for w in range(x)for i in[l[j:j-~w]for j in range(x-w)]}-{1}))

Probieren Sie es online!

total menschlich
quelle
l=list("31415...)sollte ~ 40 Zeichen sparen. Und diese Änderung können Sie map(str,i)mit nur ersetzen i.
AShelly
195 Bytes durch Entfernen von seltsamem Code.
Mr. Xcoder
194 Bytes durch Deklarationlen(l)
Mr. Xcoder
1

R, 156 123 Bytes

cat(cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))[scan()])

Super interessante Lösung. Arbeit an einem richtigen.

33 Bytes dank @Giuseppe eingespart.

R (+ Zahlen und gmp), 198 Bytes

function(n,x=unique(gmp::as.bigz(unlist(sapply(1:n,function(x)substring(gsub("[.]","",numbers::dropletPi(50)),x,x:n))))))min(length(x),sum(sapply(sapply(x[x>0&!is.na(x)],gmp::factorize),length)==1))

Richtige Lösung. Nimmt nals Eingabe.

Verwendet numbers::dropletPi(50)die ersten 50 Dezimalstellen von Pi zu erzeugen. gsubEntfernt den Dezimalpunkt. substringnimmt jede mögliche Teilzeichenfolge (Überraschung Überraschung) von pi bis zu n.

Die zurückgegebene Liste wird reduziert und in gmpdas bigzFormat von konvertiert. Dieses Format ist erforderlich, um Ganzzahlen der Länge 50 zu speichern. Es werden uniquedie eindeutigen Werte dieses Vektors verwendet. Dieses Ergebnis wird in gespeichert x.

Dann überprüfen wir die Ursprünglichkeit. Dies ist schwierig, da es eine Reihe von Randbemerkungen und Ärgernissen gibt:

  • Für hoch ngibt es ein 0in pi. Dies führt zu Teilzeichenfolgen mit einer führenden Null. as.bigzerzeugt NAs mit dem, was entfernt werden muss.

  • In einem ähnlichen Fall "0"stürzt die Teilzeichenfolge ab gmp::factorizeund muss daher ebenfalls entfernt werden.

  • Für n=1, x = 3. Was an sich in Ordnung ist, aber die bigzDarstellung von 3iterabel ist, sapplywird verwirrt und 16 Primzahlen melden. Zu diesem Zweck nehmen wir das Minimum der Länge des Vektors xund die Anzahl der darin enthaltenen Primzahlen.

  • gmp::isprimeIch kann nicht zuverlässig mit den großen Zahlen umgehen. Also verwenden wir stattdessen gmp::factorizeund überprüfen, ob die Länge der Ausgabe 1 ist.

Insgesamt entfernen wir 0und NAvon x. Wir faktorisieren alles xund überprüfen die Länge. Wir zählen die Anzahl der Vorkommen von 1und geben die zurück min(occurences, length(x)).

JAD
quelle
da bist du ja! Lassen Sie uns nun sehen, ob jemand da draußen mit einer interessanteren Lösung dies übertreffen kann. Könntest du sein!
Verwenden Sie cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))anstelle Ihres Vektors für 123 Bytes :)
Giuseppe
@ Giuseppe Schöne. Diese "Komprimierung" wird definitiv jede legitime Lösung schlagen.
JAD
Ich denke, dass es in R unmöglich ist, ohne eine Hardcodierung vorzunehmen oder ein anderes Paket einzuführen, da R nur 32-Bit-Ints hat, die mit Sicherheit keine 50-stellige Ganzzahl darstellen.
Giuseppe
1
Ja, vielleicht denke ich auch noch etwas darüber nach. 82 fest codierte Bytes
Giuseppe
0

Jelly , 59 32 Bytes

-27 Bytes dank Erik dem Outgolfer.

“!⁶⁷¬,6½ạEC.wʠ€Ẉ!+Ẉfṭ¡’Ṿḣ³ẆVQÆPS

Probieren Sie es online!

Erläuterung

“...’Ṿḣ³ẆVQÆPS

“...’           compressed string that evaluates to first 50 digits of pi (314159...)
     Ṿ          uneval; stringify
      ḣ³        first n characters of the string where n is the first command-line argument
        Ẇ       all sublists
         V      convert all elements to integers
          Q     deduplicate
           ÆP   convert all prime elements to 1 and others to 0
             S  sum
total menschlich
quelle
Warum hast du das mit Antworten Spam?
Zacharý
Weil sonst niemand antwortete und ich sowieso die Wiederholungskappe drückte. : P
totalhuman