Liste der Primzahlen unter einer Million

56

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.

Delan Azabani
quelle
12
Es handelt sich nicht um ein genaues Duplikat, sondern im Wesentlichen nur um einen Primärtest , der Bestandteil einer Reihe vorhandener Fragen ist (z. B. codegolf.stackexchange.com/questions/113 , codegolf.stackexchange.com/questions/5087 , codegolf.stackexchange). com / questions / 1977 ). FWIW, eine Richtlinie, die nicht genug befolgt wird (selbst von Leuten, die es besser wissen sollten), ist, eine Frage in der meta sandbox meta.codegolf.stackexchange.com/questions/423 vorzuschlagen, um Kritik zu üben und zu diskutieren, wie es sein kann verbessert, bevor die Leute anfangen, darauf zu antworten.
Peter Taylor
Ah, ja, ich machte mir Sorgen, dass diese Frage der Fülle von Primzahlfragen, die es bereits gibt, zu ähnlich ist.
Delan Azabani
2
@ GlennRanders-Pehrson Weil 10^6es noch kürzer ist;)
ɐɔıɐɔuʇǝɥʇs
1
Vor ein paar Jahren habe ich einen IOCCC-Eintrag eingereicht, der Primzahlen mit nur 68 Zeichen in C ausgibt
Computronium
1
@ ɐɔıɐɔuʇǝɥʇs Wie wäre es mit 1e6:-D
Titus

Antworten:

33

Mathematica , 17, 24

Nur zum Vergleich:

Prime@Range@78498

Wie in einem Kommentar erwähnt, konnte ich keine Primzahl pro Zeile angeben. Korrektur:

Column@Prime@Range@78498
Mr.Wizard
quelle
4
Prime~Array~78498auch 17 :)
Chyanog
Wäre neun Bytes in mthmca, wenn das freigegeben würde.
Michael Stern
Dies verstößt gegen die Bedingung einer Primzahl pro Ausgabezeile. Voranstellen Print/@und Beenden mit ;, um die Ausgabe einer langen Liste von NullKorrekturen zu verhindern , die 8 zusätzliche Zeichen kosten.
Celtschk
@celtschk Ich weiß nicht, ob ich das vor fünf Jahren verpasst oder ignoriert habe.
Mr.Wizard
1
Nun, ich habe definitiv verpasst, dass es von vor fünf Jahren war :-)
Celtschk
27

Python 3, 46 Bytes

k=P=1
while k<1e6:P%k and print(k);P*=k*k;k+=1

Bis die Schleife den Test erreicht k, hat sie die quadrierte Fakultät iterativ berechnet P=(k-1)!^2. Wenn kprime ist, erscheint es nicht im Produkt 1 * 2 * ... * (k-1), also ist es kein Faktor von P. Aber wenn es zusammengesetzt ist, sind alle seine Primfaktoren kleiner und so im Produkt. Das Quadrieren wird eigentlich nur benötigt, um nicht k=4fälschlicherweise als Primzahl bezeichnet zu werden.

Stärker folgt aus dem Satz von Wilson, dass, wenn kPrimzahl ist, P%kgleich ist 1. Obwohl wir nur brauchen, dass es hier nicht Null ist, ist es im Allgemeinen nützlich, dass P%kes eine Indikatorvariable dafür ist, ob kes eine Primzahl ist.

xnor
quelle
23

C 61 Zeichen

Fast genau das gleiche wie dieses (die Frage ist auch fast genau das gleiche).

n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
ugoren
quelle
Haben Sie SEG-FAULTnach dem Drucken881
manav mn
7
@Manav, vielleicht hast du ohne optimierungen kompiliert. Es basiert auf einem guten Optimierer, der die Rekursion entfernt.
Ugoren
4
Ja, -O3um gccdas Problem zu lösen !!
Manav Mn
Diese Methode ist verrückt. Ich liebe es.
Todd Lehman
2
Ich kann Sie auf 57 Bytes bringenn=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
Albert Renshaw
22

MATLAB (16) (12)

Leider wird dies in einer einzigen Zeile ausgegeben:

primes(1000000)

Dies wird jedoch durch eine einfache Matrixtransponierung gelöst:

primes(1000000)'

und ich kann einige Zeichen mit Exponentialschreibweise ausschneiden (wie in den Kommentaren vorgeschlagen):

primes(1e6)'
MBraedley
quelle
5
Verwenden 1e6statt 1000000helfen auch hier.
Orion
@orion Das würde es 11 Zeichen machen
Axoren
@ Axoren, die 'am Ende nicht enthalten
Stan Strum
20

Bash (37 Zeichen)

seq 2 1e6|factor|sed 's/.*: //g;/ /d'

(60 Zeichen)

seq 2 1000000|factor|sed -e 's/[0-9]*: //g' -e '/^.* .*$/ d'

auf meinem Computer (2,0 GHz CPU, 2 GB RAM) dauert 14 Sekunden.

saeedn
quelle
Dies kann verbessert werden, um: seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
Delan Azabani
ja, du hast Recht. Ich schrieb meinen sed Befehl sauber, nicht Golf: P
saeedn
3
seq 1e6|factor|awk '$0=$2*!$3'ist etwas kürzer.
Dennis
1
seq, factor und sed sind externe Programme. Dies kann auch der Fall sein, c pwenn c ein Symlink zu cat und p eine Textdatei mit Primzahlen bis zu einer Million ist. Können Sie dies mit Shell-Builtins tun?
Technosaurus
7
@technosaurus seqund factorsind in coreutils, so ist es legitim. sedist auch ziemlich allgegenwärtig. coreutilskann wie ein eingebauter behandelt werden. Bash ohne Coreutils ist wie C ++ ohne STL.
16

J, 21 Zeichen

1[\p:i.(_1 p:1000000)

das kann gekürzt werden

1[\p:i.78498

Wenn Sie wissen, wie viele Primzahlen es unter 1000000 gibt.

Gareth
quelle
2
Verwenden Sie enfile items ,.anstelle von 1 [\\, um ein Zeichen zu speichern. Entfernen Sie die unnötigen Klammern, und verwenden Sie Exponentialnotation: 1e6.
Omar
Kam mit diesem: ,.i.&.(p:^:_1)1e6Nicht kürzer (nach dem Anwenden von @ Omars Vorschlägen), aber ich fand die Verwendung von unter interessant.
kaoD
10

PowerShell, 47 44 Bytes

Sehr langsam, aber das kürzeste, das ich finden konnte.

$p=2..1e6;$p|?{$n=$_;!($p-lt$_|?{!($n%$_)})}

PowerShell, 123 Byte

Das geht viel schneller; alles andere als optimal, aber ein guter Kompromiss zwischen Effizienz und Kürze.

 $p=2..1e6;$n=0
 while(1){$p=@($p[0..$n]|?{$_})+($p[($n+1)..($p.count-1)]|?{$_%$p[$n]});$n++;if($n-ge($p.count-1)){break}}
 $p
Rynant
quelle
9

Rubin 34

require'prime';p Prime.take 78498
Holeth
quelle
9

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:

seq 1e6|factor|awk '$0=$2*!$3'

Wie es funktioniert

seq 1e6

listet alle positiven ganzen Zahlen bis zu 1.000.000 auf.

factor

Faktoren sie eins nach dem anderen. Für die ersten zehn ist die Ausgabe wie folgt:

1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5

Endlich,

awk '$0=$2*!$3'

Ändert die gesamte Zeile ( $0) in das Produkt des zweiten Feldes (erster Primfaktor) und die logische Negation des dritten Feldes ( 1wenn das ein Primfaktor oder weniger ist, 0sonst).

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.

Dennis
quelle
4
awk '$0=$2*!$3'ist verdammt cool!
Yeti
8

Ruby 50 41

require'mathn'
p (2..1e6).select &:prime?
Cristian Lupascu
quelle
2
Keine Notwendigkeit .to_a, da Enumerable bereits enthält select. 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)
Ventero
@Ventero vielen Dank! Ich wusste nichts über das Symbol # to_proc. Ich muss den Abkürzungen, die Ruby anbietet, mehr Aufmerksamkeit schenken.
Cristian Lupascu
2
Kürzere Version require'prime';p Prime.take 78498.
Holeth
@ ŁukaszNiemier Großartig! Ich finde das so anders, dass man es als separate Antwort posten kann.
Cristian Lupascu
Gute Verwendung von einigen guten alten Country Boy Mathn
DoctorHeckle
8

Bash, 37

Werde mehr Golf spielen, wenn ich kann ...

Das meiste versucht das factorumständliche Ausgabeformat zu analysieren .

seq 1e6|factor|grep -oP "(?<=: )\d+$"

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

seq 1e6|factor|egrep ':.\S+$'|grep -oE '\S+$'

quelle
2
Wow - ich bin noch nie darauf gestoßen factor, aber da ist es genau dort in coreutils!
Digitales Trauma
1
Rasiere einen Charakter ab: seq 1e6|factor|grep -oP "(?<=: )\d+$"mit einem Perl-Grep-Lookbehind
Digitales Trauma
@ DigitalTrauma wie funktioniert das
1
-PAktiviert 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 -oOption nur eine übereinstimmende Zahl nach dem Doppelpunkt angibt, dh nur Zahlen angibt, bei denen es nur einen Faktor gibt, dh Primzahl.
Digitales Trauma
@DigitalTrauma hinzugefügt
8

Python 3.x: 66 Zeichen

for k in range(2,10**6):
 if all(k%f for f in range(2,k)):print(k)

Effizientere Lösung: 87 Zeichen

Basierend auf dem Sieb des Eratosthenes.

p=[];z=range(2,10**6)
while z:f=z[0];p+=[f];z=[k for k in z if k%f]
for k in p:print(k)
dan04
quelle
1
Der erste druckt fälschlicherweise 0und 1. Sie können dies beheben, indem Sie stattdessen verwenden range(2,10**6). Ich denke auch, dass die ifAnweisung in einer separaten Zeile vom Ausgang stehen muss, da sonst forein Fehler auftritt.
13.
@ xnor: Es wurde behoben.
Dan04
8

Haskell, 51

mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]
pt2121
quelle
Sie können ändern , mapM_um mapMRückgabewert, wird nicht gedruckt, und das ist Code Golf. ;)
Dogbert
Warum gibt es nach dem Ausdruck und in (> 0) zusätzliche Leerzeichen?
stolzer Haskeller
schöner Fang! danke
pt2121
Sie können 999999 durch 10 ^ 6 ersetzen. Und bitte aktualisieren Sie Ihre Byteanzahl - 63 kann möglicherweise nicht richtig sein.
user2845840
@ user2845840 ok danke. gute Idee!
pt2121
8

APL, 15

p~,p∘.×p←1↓⍳1e6

Mein Dolmetscher hatte Probleme mit dem Gedächtnis, aber es funktioniert theoretisch.

TwiNight
quelle
Wie? Können Sie eine Beschreibung geben?
Rasmus Damgaard Nielsen
Du brauchst ein vor, um eine Nummer pro Zeile zu machen, und das brauchst du nicht ,.
Adám
@RasmusDamgaardNielsen sind die ersten ganzen Zahlen. 1↓lässt den ersten fallen. p←weist zu p. p∘.×pmacht eine Multiplikationstabelle. p~Entfernt von p alles, was rechts ist. ( ,wird nicht benötigt, es reist den Tisch in eine Liste.)
Adám
8

Perl, 49 Bytes

Regulärer Ausdruck Kung Fu :)

for(1..1E6){(1x$_)=~/^(11+?)\1+$/ or print"$_\n"}

Ungolfed-Version:

for(1 .. 1_000_000) { 
    (1x$_) =~ /^(11+?)\1+$/ or print "$_\n";
}

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

Gowtham
quelle
2
hat mich dazu inspiriert, eine perl6-version zu schreiben. Auch 1000000kann geschrieben werden10**6
pabo
1
Außerdem kann 1000000
mob
Aktualisiert meine Antwort. Thanks @mob
Gowtham
War schon immer ein beliebter Regex von mir, aber Sie müssen sich daran erinnern, dass er spektakulär versagt, sobald Sie höhere Zahlen erreicht haben - aufgrund der Tatsache, dass er große Zahlen in unäre Zahlen umwandelt. Je nach Konfiguration der Sprache (und Ihrer Maschine)
funktioniert
7

Julia, 11

primes(10^6)

Es sieht so aus, als würden eingebaute Ins positiv bewertet, und ich brauchte mehr Worte für eine längere Antwort.

gggg
quelle
7

J (15 oder 9)

Ich kann diesen Beat von Mathematica nicht glauben (auch wenn es nur eine Single mit 2 Zeichen ist)

a#~1 p:a=:i.1e6

Oder:

p:i.78498
ɐɔıɐɔuʇǝɥʇs
quelle
1
... The output format should be one number per line of output.Deshalb beginnt meine Antwort mit 1[\ .
Gareth
6

gs2, 5 bytes

In CP437 codiert:

∟)◄lT

1C 29Drückt eine Million, 11 6Cist Primzahlen unten, 54ist Linien zeigen.

Lynn
quelle
5

GolfScript, 22/20 (20/19) Bytes

n(6?,:|2>{(.p|%-.}do:n

Auf Kosten der Geschwindigkeit kann der Code zwei Bytes kürzer gemacht werden:

n(6?,:|2>.{|%2>-}/n*

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:

n(6?,:|2>{(.p|%-.}do
n(6?,:|2>.{|%2>-}/`

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:

  1. Stellen Sie A = [ 2 3 4 … 999,999 ]und ein| = [ 0 1 2 … 999,999 ] .

  2. Einstellen N = A[0]und druckenN .

  3. Sammle jedes N-te Element von |in C. Dies sind die Vielfachen vonN .

  4. einstellen A = A - C .

  5. Wenn Aes nicht leer ist, gehe zurück zu 2.

n(6?   # Push "\n".pop() ** 6 = 1,000,000.
,:|    # Push | = [ 0 1 2 … 999,999 ].
,2>    # Push A = [ 2 3 4 … 999,999 ].
{      #
  (    # Unshift the first element (“N”) of “A”.
  .p   # Print “N”.
  |%   # Collect every N-th element from “A” into a new array, starting with the first.
  -    # Take the set difference of “A” and the array from above.
  .    # Duplicate the set difference.
}do    # If the set difference is non-empty, repeat.
:n     # Store the empty string in “n”, so no final LF will get printed.

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:

Bound     | Trial division     | Sieve (slow)       | Wilson's theorem | Sieve (fast)
----------+--------------------+--------------------+------------------+----------------
1,000     | 2.47 s             | 0.06 s             | 0.03 s           | 0.03 s
10,000    | 246.06 s (4.1 m)   | 1.49 s             | 0.38 s           | 0.14 s
20,000    | 1006.83 s (16.8 m) | 5.22 s             | 1.41 s           | 0.38 s
100,000   | ~ 7 h (estimated)  | 104.65 (1.7 m)     | 35.20 s          | 5.82 s
1,000,000 | ~ 29 d (estimated) | 111136.97s (3.1 h) | 3695.92 s (1 h)  | 418.24 s (7 m)
Dennis
quelle
Ist das "langsame" Sieb nur ein Sieb von Eratosthenes?
Dorukayhan
Beide sind. Die langsame Version ist nur eine schreckliche Implementierung.
Dennis
5

NARS2000 APL, 7 Zeichen

⍸0π⍳1e6
Der Bienenstock
quelle
3
Willkommen bei Programming Puzzles & Code Golf!
Dennis
4

Golfscript 26 25 24

Bearbeiten (ein weiteres Zeichen dank Peter Taylor gespeichert):

10 6?,{:x,{)x\%!},,2=},`

Alter Code:

10 6?,{.,{)\.@%!},,2=*},`

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:

10 2?,{:x,{)x\%!},,2=},`
Cristian Lupascu
quelle
Sie können durch das Ersetzen eines Zeichens speichern \;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$\%!}?=},`
Peter Taylor
@ PeterTaylor Danke, mit Multiplikation gibt es einen sehr ordentlichen Trick.
Cristian Lupascu
Es gibt noch ein Zeichen, das mit einer Variablen gespart wird: Ersetzen Sie .,mit :x,und \.@mit x\ (Leerzeichen aufgrund von Problemen mit MD in Kommentaren) und entfernen Sie *.
Peter Taylor
@PeterTaylor gut, danke! Ich habe meinen Code bearbeitet.
Cristian Lupascu
4

CJam - 11

1e6,{mp},N*

1e6,- Array von 0 ... 999999
{mp},- Primzahlen auswählen
N*- mit Zeilenumbrüchen verbinden

aditsu
quelle
1
Ist CJam nicht aktueller als diese Frage?
Peter Taylor
@ Peter Taylor oh, ja, es ist
aditsu
4

GolfScript, 25 (24) Bytes

!10 6?,2>{.(@*.)@%!},n*\;

Wenn das in der bearbeiteten Frage angegebene Ausgabeformat nicht berücksichtigt wird, kann ein Byte gespeichert werden:

!10 6?,2>{.(@*.)@%!},`\;

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

                                                      (n - 1)!  = -1 (mod n)

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Benchmarks

Schneller als die Probedivision, aber langsamer als das Sieb von Eratosthenes. Siehe meine andere Antwort .

Dennis
quelle
3

C, 91 88 85 82 81 80 76 72 Zeichen

main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}

Der Algorithmus ist schrecklich ineffizient, aber da wir Code-Golf spielen, sollte das keine Rolle spielen.

Gareth
quelle
1
Sie können es leicht verkürzen: 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)
Ali1S232
Wie ist isicher, 0 zu sein? Ich denke, wenn Sie ein Argument vorbringen, wird es scheitern. Ich denke auch, dass jes eine Art Tippfehler geben wird. Bin mir baber nicht sicher .
Erik der Outgolfer
3

Mathematica 25

Vorausgesetzt, Sie kennen die Anzahl der Primzahlen nicht unter 10 ^ 6:

Prime@Range@PrimePi[10^6]
DavidC
quelle
3

J, 16 Zeichen

1]\(#~1&p:)i.1e6

Ohne die Ausgabeformatanforderung kann dies auf 13 Zeichen reduziert werden :

(#~1&p:)i.1e6

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) yist im Grunde filter, wo fein Boolescher Wert für jedes Element in zurückgegeben wird y. i.1e6ist der Bereich von ganzen Zahlen [0,1000000) und 1&p:ist eine boolesche Funktion, die 1 für Primzahlen zurückgibt.

rationalis
quelle
3

R, 45 43 Zeichen

for(i in 2:1e6)if(sum(!i%%2:i)<2)cat(i," ")

Geben 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.

Plannapus
quelle
Die erste von diesem Code erzeugte Zahl ist 1, aber 1 ist keine Primzahl.
Sven Hohenstein
@SvenHohenstein Danke, korrigiert.
Plannapus
3

Bash (433643)

Mein (nicht so kluger) Versuch war es, das Produkt mit Faktor zu faktorisieren.

factor ${PRODUCT}

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.

  factor 30

Na ja, ich habe es versucht.

Kevin Cox
quelle
+1 Diese Antwort ist wirklich teuflisch. Das Ergebnis ist nicht ganz vorausberechnet (es spart eine Menge Zeichen) und es ist viel schrecklicher zu berechnen :) Es ist möglicherweise auch ein Beispiel, das die optimierte factorLeistung viel schlechter macht als der grundlegende Versuchsteilungsalgorithmus.
Orion
3

C #, 70

Enumerable.Range(1,1e6).Where(n=>Enumerable.Range(2,n).All(x=>x%n!=0))

Sie werden hier aber für eine lange Zeit nicht viel sehen ...

Es istNotALie.
quelle
Es gibt mehrere Gründe, warum dies falsch ist. (1) Sie können nicht implizit von a double 1e6nach a konvertieren int, sondern intwerden von benötigt Range. (2) Das Innere Rangemuss höchstens n-2Begriffe nehmen, sonst wirst du testen n % nwas klar ist 0. (3) Du schreibst x%nwann du willst n%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.
Jeppe Stig Nielsen