Dies ist meine erste Code-Golf-Frage, und zwar eine sehr einfache. Deshalb entschuldige ich mich im Voraus, wenn ich möglicherweise gegen Community-Richtlinien verstoßen habe.
Die Aufgabe besteht darin, alle Primzahlen unter einer Million in aufsteigender Reihenfolge auszudrucken. Das Ausgabeformat sollte eine Zahl pro Ausgabezeile sein.
Das Ziel ist, wie bei den meisten Code-Golf-Einsendungen, die Minimierung der Codegröße. Die Optimierung für die Laufzeit ist ebenfalls ein Bonus, aber ein sekundäres Ziel.
code-golf
kolmogorov-complexity
primes
Delan Azabani
quelle
quelle
10^6
es noch kürzer ist;)1e6
:-DAntworten:
Mathematica ,
17,24Nur zum Vergleich:
Wie in einem Kommentar erwähnt, konnte ich keine Primzahl pro Zeile angeben. Korrektur:
quelle
Prime~Array~78498
auch 17 :)Print/@
und Beenden mit;
, um die Ausgabe einer langen Liste vonNull
Korrekturen zu verhindern , die 8 zusätzliche Zeichen kosten.Python 3, 46 Bytes
Bis die Schleife den Test erreicht
k
, hat sie die quadrierte Fakultät iterativ berechnetP=(k-1)!^2
. Wennk
prime ist, erscheint es nicht im Produkt1 * 2 * ... * (k-1)
, also ist es kein Faktor vonP
. Aber wenn es zusammengesetzt ist, sind alle seine Primfaktoren kleiner und so im Produkt. Das Quadrieren wird eigentlich nur benötigt, um nichtk=4
fälschlicherweise als Primzahl bezeichnet zu werden.Stärker folgt aus dem Satz von Wilson, dass, wenn
k
Primzahl ist,P%k
gleich ist1
. Obwohl wir nur brauchen, dass es hier nicht Null ist, ist es im Allgemeinen nützlich, dassP%k
es eine Indikatorvariable dafür ist, obk
es eine Primzahl ist.quelle
C 61 Zeichen
Fast genau das gleiche wie dieses (die Frage ist auch fast genau das gleiche).
quelle
SEG-FAULT
nach dem Drucken881
-O3
umgcc
das Problem zu lösen !!n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
MATLAB
(16)(12)Leider wird dies in einer einzigen Zeile ausgegeben:
Dies wird jedoch durch eine einfache Matrixtransponierung gelöst:
und ich kann einige Zeichen mit Exponentialschreibweise ausschneiden (wie in den Kommentaren vorgeschlagen):
quelle
1e6
statt1000000
helfen auch hier.'
am Ende nicht enthaltenBash (37 Zeichen)
(60 Zeichen)
auf meinem Computer (2,0 GHz CPU, 2 GB RAM) dauert 14 Sekunden.
quelle
seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
seq 1e6|factor|awk '$0=$2*!$3'
ist etwas kürzer.c p
wenn c ein Symlink zu cat und p eine Textdatei mit Primzahlen bis zu einer Million ist. Können Sie dies mit Shell-Builtins tun?seq
undfactor
sind incoreutils
, so ist es legitim.sed
ist auch ziemlich allgegenwärtig.coreutils
kann wie ein eingebauter behandelt werden. Bash ohne Coreutils ist wie C ++ ohne STL.J, 21 Zeichen
das kann gekürzt werden
Wenn Sie wissen, wie viele Primzahlen es unter 1000000 gibt.
quelle
,.
anstelle von 1 [\\, um ein Zeichen zu speichern. Entfernen Sie die unnötigen Klammern, und verwenden Sie Exponentialnotation:1e6
.,.i.&.(p:^:_1)1e6
Nicht kürzer (nach dem Anwenden von @ Omars Vorschlägen), aber ich fand die Verwendung von unter interessant.PowerShell,
4744 BytesSehr langsam, aber das kürzeste, das ich finden konnte.
PowerShell, 123 Byte
Das geht viel schneller; alles andere als optimal, aber ein guter Kompromiss zwischen Effizienz und Kürze.
quelle
Rubin 34
quelle
Bash, 30 Bytes
Da saeedn nicht auf meinen Vorschlag eingeht - der sowohl kürzer als auch schneller ist als sein Ansatz -, dachte ich, ich würde meine eigene Antwort posten:
Wie es funktioniert
listet alle positiven ganzen Zahlen bis zu 1.000.000 auf.
Faktoren sie eins nach dem anderen. Für die ersten zehn ist die Ausgabe wie folgt:
Endlich,
Ändert die gesamte Zeile (
$0
) in das Produkt des zweiten Feldes (erster Primfaktor) und die logische Negation des dritten Feldes (1
wenn das ein Primfaktor oder weniger ist,0
sonst).Dies ersetzt Zeilen, die Primzahlen entsprechen, durch die Zahl selbst und alle anderen Zeilen durch Nullen. Da awk nur wahrheitsgemäße Werte ausgibt, werden nur Primzahlen ausgegeben.
quelle
awk '$0=$2*!$3'
ist verdammt cool!Ruby
5041quelle
.to_a
, da Enumerable bereits enthältselect
. Sie können auch die Kurzschreibweise für Symbol # to_proc verwenden , um es weiter zu verkürzen:p (2..1e6).select &:prime?
(1 ist keine Primzahl)require'prime';p Prime.take 78498
.Bash, 37
Werde mehr Golf spielen, wenn ich kann ...
Das meiste versucht das
factor
umständliche Ausgabeformat zu analysieren .Die Ausführung auf meinem Computer dauert ungefähr 5,7 Sekunden.
(Es ist einfach passiert, dass mein Beitrag der erste war , der auf der zweiten Seite der Antworten auftauchte, also wird es niemand sehen ...)
Alte Lösung
Dies ist länger und langsamer (dauert 10 Sekunden).
quelle
factor
, aber da ist es genau dort in coreutils!seq 1e6|factor|grep -oP "(?<=: )\d+$"
mit einem Perl-Grep-Lookbehind-P
Aktiviert reguläre Ausdrücke im Perl-Stil.(?<=: )
ist ein positiver Look für den String ":". Grundsätzlich besagt dies, dass ":" vor den Übereinstimmungen stehen muss\d+$
, aber nicht Teil der Übereinstimmung ist, sodass die-o
Option nur eine übereinstimmende Zahl nach dem Doppelpunkt angibt, dh nur Zahlen angibt, bei denen es nur einen Faktor gibt, dh Primzahl.Python 3.x: 66 Zeichen
Effizientere Lösung: 87 Zeichen
Basierend auf dem Sieb des Eratosthenes.
quelle
0
und1
. Sie können dies beheben, indem Sie stattdessen verwendenrange(2,10**6)
. Ich denke auch, dass dieif
Anweisung in einer separaten Zeile vom Ausgang stehen muss, da sonstfor
ein Fehler auftritt.Haskell, 51
quelle
mapM_
ummapM
Rückgabewert, wird nicht gedruckt, und das ist Code Golf. ;)APL, 15
Mein Dolmetscher hatte Probleme mit dem Gedächtnis, aber es funktioniert theoretisch.
quelle
⍪
vor, um eine Nummer pro Zeile zu machen, und das brauchst du nicht,
.⍳
sind die ersten ganzen Zahlen.1↓
lässt den ersten fallen.p←
weist zu p.p∘.×p
macht eine Multiplikationstabelle.p~
Entfernt von p alles, was rechts ist. (,
wird nicht benötigt, es reist den Tisch in eine Liste.)Perl, 49 Bytes
Regulärer Ausdruck Kung Fu :)
Ungolfed-Version:
Es hat nicht einmal 10% Fortschritt gemacht, während ich diesen Beitrag schreibe!
Quelle für die Regex: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
quelle
1000000
kann geschrieben werden10**6
Julia, 11
Es sieht so aus, als würden eingebaute Ins positiv bewertet, und ich brauchte mehr Worte für eine längere Antwort.
quelle
J (15 oder 9)
Ich kann diesen Beat von Mathematica nicht glauben (auch wenn es nur
eine Singlemit 2 Zeichen ist)Oder:
quelle
... The output format should be one number per line of output.
Deshalb beginnt meine Antwort mit1[\
.gs2, 5 bytes
In CP437 codiert:
1C 29
Drückt eine Million,11 6C
ist Primzahlen unten,54
ist Linien zeigen.quelle
GolfScript, 22/20 (20/19) Bytes
Auf Kosten der Geschwindigkeit kann der Code zwei Bytes kürzer gemacht werden:
Wenn das in der bearbeiteten Frage angegebene Ausgabeformat nicht beachtet wird (wie viele der vorhandenen Antworten), können zwei Bytes in der schnellen und eines in der langsamen Version gespeichert werden:
Dadurch wird nach den Primzahlen für die schnelle Version eine zusätzliche LF ausgegeben, und die Primzahlen werden als Array für die langsame Version gedruckt.
Wie es funktioniert
Beide Versionen sind Implementierungen des Siebs von Eratosthenes .
Die schnelle Version macht folgendes:
Stellen Sie
A = [ 2 3 4 … 999,999 ]
und ein| = [ 0 1 2 … 999,999 ]
.Einstellen
N = A[0]
und druckenN
.Sammle jedes N-te Element von
|
inC
. Dies sind die Vielfachen vonN
.einstellen
A = A - C
.Wenn
A
es nicht leer ist, gehe zurück zu 2.Die langsame Version funktioniert auf ähnliche Weise, aber anstatt nacheinander ein Vielfaches des Minimums von „A“ (das immer eine Primzahl ist) zu entfernen, werden ein Vielfaches aller positiven Ganzzahlen unter 1.000.000 entfernt.
Wettbewerbsfähigkeit
Ohne eingebaute mathematische Funktionen zur Faktorisierung oder Überprüfung der Primalität sind alle GolfScript-Lösungen entweder sehr umfangreich oder sehr ineffizient.
Ich bin zwar noch weit davon entfernt, effizient zu sein, aber ich denke, ich habe ein anständiges Verhältnis von Geschwindigkeit zu Größe erreicht. Zum Zeitpunkt der Übermittlung scheint dieser Ansatz der kürzeste zu sein, der keine der oben genannten integrierten Funktionen verwendet. Ich sage scheint, weil ich keine Ahnung habe, wie einige der Antworten funktionieren ...
Ich habe alle vier eingereichten GolfScript-Lösungen verglichen: w0lfs (Versuchsabteilung), meine andere Antwort (Wilsons Theorem) und die beiden dieser Antworten. Das waren die Ergebnisse:
quelle
NARS2000 APL, 7 Zeichen
quelle
Golfscript
26 2524Bearbeiten (ein weiteres Zeichen dank Peter Taylor gespeichert):
Alter Code:
Dieser Code hat nur theoretischen Wert, da er unglaublich langsam und ineffizient ist. Ich denke, es könnte Stunden dauern, bis es läuft.
Wenn Sie es testen möchten, versuchen Sie zum Beispiel nur die Primzahlen bis 100:
quelle
\;
mit*
. (Sie können für die aktuelle Anzahl der Zeichen auch viel schneller werden, indem Sie den ersten Teiler finden, anstatt alle:10 6?,2>{.),2>{1$\%!}?=},`
.,
mit:x,
und\.@
mitx\
(Leerzeichen aufgrund von Problemen mit MD in Kommentaren) und entfernen Sie*
.CJam - 11
1e6,
- Array von 0 ... 999999{mp},
- Primzahlen auswählenN*
- mit Zeilenumbrüchen verbindenquelle
GolfScript, 25 (24) Bytes
Wenn das in der bearbeiteten Frage angegebene Ausgabeformat nicht berücksichtigt wird, kann ein Byte gespeichert werden:
Dadurch werden die Primzahlen als Array (wie bei vielen anderen Lösungen) und nicht als Array pro Zeile gedruckt.
Wie es funktioniert
Die allgemeine Idee ist, den Satz von Wilson zu verwenden , der besagt, dass n > 1 genau dann Primzahl ist, wenn
Benchmarks
Schneller als die Probedivision, aber langsamer als das Sieb von Eratosthenes. Siehe meine andere Antwort .
quelle
Java, 110 Bytes
Verwendung der unären Division durch Regex als Primärtest.
quelle
C,
9188858281807672 ZeichenDer Algorithmus ist schrecklich ineffizient, aber da wir Code-Golf spielen, sollte das keine Rolle spielen.
quelle
main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}
oder eine Idee wie diese (da ich es tatsächlich nicht kompiliert habe)i
sicher, 0 zu sein? Ich denke, wenn Sie ein Argument vorbringen, wird es scheitern. Ich denke auch, dassj
es eine Art Tippfehler geben wird. Bin mirb
aber nicht sicher .Mathematica 25
Vorausgesetzt, Sie kennen die Anzahl der Primzahlen nicht unter 10 ^ 6:
quelle
J, 16 Zeichen
Ohne die Ausgabeformatanforderung kann dies auf 13 Zeichen reduziert werden :
1]\
Nimmt einfach das Primzahlen-Array von Rang 1, wandelt es in ein Array von Rang 2 um und platziert jedes Primzeichen in einer eigenen Zeile. Das Standardausgabeformat des Interpreters wandelt die Liste mit einer Zeile in ein Primzeichen pro Zeile um.(#~ f) y
ist im Grundefilter
, wof
ein Boolescher Wert für jedes Element in zurückgegeben wirdy
.i.1e6
ist der Bereich von ganzen Zahlen [0,1000000) und1&p:
ist eine boolesche Funktion, die 1 für Primzahlen zurückgibt.quelle
R,
4543 ZeichenGeben Sie es für jede Zahl x von 2 bis 1e6 einfach aus, wenn die Zahl von x mod 2 bis x, die gleich 0 ist, kleiner als 2 ist.
quelle
Bash (433643)
Mein (nicht so kluger) Versuch war es, das Produkt mit Faktor zu faktorisieren.
Leider ist das Produkt bei großen Stückzahlen natürlich riesig. Es dauerte auch mehr als 12 Stunden zu laufen. Ich habe mich entschieden, es zu posten, weil ich es für einzigartig hielt.
Hier ist der vollständige Code.
Wenn es Primzahlen unter sechs wären, wäre es vernünftig.
Na ja, ich habe es versucht.
quelle
factor
Leistung viel schlechter macht als der grundlegende Versuchsteilungsalgorithmus.C #, 70
Sie werden hier aber für eine lange Zeit nicht viel sehen ...
quelle
double
1e6
nach a konvertierenint
, sondernint
werden von benötigtRange
. (2) Das InnereRange
muss höchstensn-2
Begriffe nehmen, sonst wirst du testenn % n
was klar ist0
. (3) Du schreibstx%n
wann du willstn%x
. Wenn Sie diese Probleme beheben, funktioniert Folgendes:Enumerable.Range(2,999999).Where(n=>Enumerable.Range(2,n-2).All(x=>n%x!=0))
Die Zahlen werden jedoch immer noch nicht ausgegeben. Die Anforderung war eine pro Zeile.