Problem
Das Ziel ist, wie der Titel sagt, die n-te Primzahl so zu finden, dass die Primzahl-1 durch n teilbar ist.
Erläuterung
Hier ist ein Beispiel, damit Sie die Frage verstehen. Dies ist nicht unbedingt die Art und Weise, wie sie gelöst werden sollte. Es ist nur ein Weg, um die Frage zu erklären
Bei einer Eingabe von 3 würden wir uns zuerst alle Primzahlen ansehen
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 ...
Dann wählen wir die Primzahlen so aus, dass die Primzahl - 1 durch n teilbar ist (in diesem Fall 3).
7 13 19 31 37 43 61 67 73 79 97 103 107 109 127 ...
Wir wählen dann den n-ten Term in dieser Reihenfolge aus
Wir würden 19 für eine Eingabe von 3 ausgeben
Hinweis
Wir können uns dies auch als die n-te Primzahl in der Folge {1, n + 1, 2n + 1, 3n + 1 ... kn + 1} vorstellen, wobei k eine beliebige natürliche Zahl ist
Testfälle
1 --> 2
2 --> 5
3 --> 19
4 --> 29
100 --> 39301
123 --> 102337
code-golf
number
number-theory
primes
Ando Bando
quelle
quelle
Antworten:
05AB1E ,
98 Bytes05AB1E verwendet die CP-1252- Codierung.
Dank Osable wurde ein Byte gespeichert
Probieren Sie es online!
Erläuterung
quelle
µN¹*>Dp½
die Idee gekommen, die ein Byte spart und die Berechnung beschleunigt.Python 2, 58 Bytes
quelle
Mathematica, 48 Bytes
Unbenannte Funktion, die ein einzelnes Argument verwendet, das sie benennt
n
. Erzeugt eine Liste der erstenn^3
Primzahlen, wählt die Primzahlen aus, die zu 1 Modulo kongruent sindn
, und nimmt dann dasn
dritte Element des Ergebnisses. Es läuft in einigen Sekunden am Eingang 123.Es ist derzeit nicht bekannt, ob es unter den ersten
n^3
Primzahlen immer nur eine einzige Primzahl gibt, die zu 1 Modulo kongruent istn
, viel wenigern
.n
Unter der Annahme der verallgemeinerten Riemannschen Hypothese kann der Algorithmus jedoch (zumindest für große ) als richtig erwiesen werden !quelle
Haskell,
5947 BytesAnwendungsbeispiel:
f 4
->29
.Wie es funktioniert:
Bearbeiten: Vielen Dank an @Damien für 12 Bytes, indem der Teilbarkeitstest entfernt und zunächst nur die Vielfachen betrachtet werden.
quelle
f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n
Gelee , 9 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Java 7, 106 Bytes
Ungolfed:
Testcode:
Versuchen Sie es hier (letzten Testfall führt zu einer Zeitüberschreitung auf ideone)
Ausgabe:
quelle
System.out.println
werden meistens hinzugefügt, damit Sie sehen, welche Eingabe ich verwendet habe, um die angezeigte Ausgabe zu geben, und alles wird auch angegeben, falls jemand es in seine IDE kopieren und einfügen möchte, um damit herumzuspielen.Nasm 679 Bytes (Anweisung Intel 386 CPU 120 Bytes)
Dies ist eine ungolfed und die Ergebnisse
quelle
Eigentlich 13 Bytes
Golfvorschläge willkommen! Probieren Sie es online!
Ungolfing
quelle
Common Lisp, 162 Bytes
Verwendung:
Ungolfed:
Einige dieser
loop
Konstrukte können wahrscheinlich zudo
Schleifen verkürzt werden, aber das ist, was ich jetzt habe.quelle
MATL , 12 Bytes
Probieren Sie es online!
(Bei der Eingabe tritt
123
im Online-Compiler eine Zeitüberschreitung auf, sie funktioniert jedoch offline.)Erläuterung
quelle
Perl,
7776 + 1 = 77 BytesVerwendet den Regex prime-testing, um festzustellen, ob
$p
es sich um eine Primzahl handelt, und stellt sicher, dass sie zu 1 mod der Eingabe kongruent ist (die einzigen nicht-negativen Ganzzahlen unter 2 sind 0 und 1, aber es kann nicht 0 sein, wenn es eine Primzahl ist, also muss es sein 1. spart 1 Byte mehr==1
).quelle
(1 x++$.)!~/^(11+?)\1+$/&&($.%$_<2)&&push@a,$.while@a<$_;say$a[-1]
(worüber ich in meinem vorherigen Kommentar gesprochen habe). Allerdings scheint die Ausgabe (von beiden Versionen) für mindestens 2 und 3 falsch ...Mathematica 44 Bytes
Sehr schnell. Verwendet die Idee aus dem "Hinweis"
Ausgabe
quelle
Perl 6 ,
46 3937 Bytesquelle
Java 8, 84 Bytes
Golf gespielt
Ungolfed
Erläuterung
Lösung inspiriert von mehreren anderen Antworten. Die Funktion ist ein Lambda, das ein einzelnes int erwartet.
Das
n>1?i:2
ist ein billiger Hack, weil ich keinen besseren Weg finden könnte, den Fall von n = 1 zu betrachten.Diese Lösung läuft auch bei Ideone ab, wurde jedoch für alle Testfälle getestet. Es tritt eine Zeitüberschreitung auf, weil ich die explizite
j<i
Prüfung in der inneren Schleife ausgeführt habe , um ein paar Bytes zu sparen . Es ist meistens impliziert durchi%j>0
... außer im Fall voni=1
undj=2
(die allererste Iteration), in welchem Fall die Schleife läuft, bis j überläuft (nehme ich an). Dann funktioniert es problemlos für alle nachfolgenden Iterationen.Eine Version, bei der keine Zeitüberschreitung auftritt und die einige Bytes länger ist, finden Sie hier!
quelle
Schläger 109 Bytes
Ungolfed:
Testen:
Ausgabe:
quelle
Ruby 64 Bytes
So genannt:
Diese Befehlszeilen-App funktioniert auch:
so genannt
aber ich bin nicht so sicher, wie ich die Zeichen zählen soll. Ich denke, ich kann den Namen der Sprache ignorieren, muss aber das
-rprime
Leerzeichen und vor dem Namen des Skripts einfügen, damit er mit 63 etwas kürzer ist. . .quelle
R, 72 Bytes
Schrecklich ineffizient und langsam, aber es funktioniert. Es liest die Eingabe von stdin und verwendet dann die
isPrime
Funktion aus demnumbers
Paket, um die Primzahlen zu finden. Der Rest prüft nur, obprime - 1
durch teilbar istn
.quelle
JavaScript (ES6), 65 Byte
Verwendet den regexp-Primalitätstester, da er a) 8 Byte kürzer und b) weniger rekursiv ist als mein rekursiver Ansatz.
quelle
Axiom 64 Bytes
weiß jemand, wie man mit Axiom-Streams schreibt? ... ein Beispiel
Typ: Tuple NonNegativeInteger
quelle