Sieb des Eratosthenes

[erdbeermarmelade]

Hallo zusammen,

ich habe mich neulich mal mit dem Sieb des Eratosthenes auseinander gesetzt und versucht, dass Ding in Perl zu schreiben. Kurz und knackig sollte es sein. Hier das Ergebnis (Ausgabe aller Primzahlen bis 100):

for($i=0,@p=(2..100);$p[$i]<=int(sqrt($#p));$i++)

{$p[$_]%$p[$i]==0 && $p[$_]!=$p[$i] && splice @p,1,$_ for reverse 0..$#}

print 'Primzahlen: ', join(', ', @p), "\n";

Darauf bekam ich von nem Bekannten die Antwort:

my @p = (2..100);

@p = do {my $d = $_; grep {$_ % $d or $_ == $d} @p} for @p;

print 'Primzahlen: ', join (', ', @p), "\n";

Sieht einer/eine von Euch ne Moeglichkeit das Ding noch kuerzer zu friemeln?

Danke fuer Eure Hilfe,

Erdbeermarmelade

[erdbeermarmelade]

Kleine Korrektur. Es sollte im ersten Code, erste Zeile so lauten (die 100):

for($i=0,@p=(2..100);$p[$i]<=int(sqrt(100));$i++)

, denn sonst kommt Unsinn bei raus.. Sorry!

[.vash]

Ich habe leider nichts zum eigentlichen Thema beizutragen:

Es gibt ja viele Ansichten übers Programmieren. Eine behauptet: Code soll so leserlich und damit verstehbar sein, so dass sich die Dokumentation praktisch erübrigt.

Meine Frage wäre nun was Du davon hast die Primzahlen noch kompakter zu berechnen. Es ist ja keine Frage des Algorithmus, der ist ja immer der selbe.

Um Deine Frage zu beantworten: Versuche einfach mal ein paar überflüssige Leerzeichen zu streichen.

[erdbeermarmelade]

So, das Thema raubt mir den letzten Nerv!

Kuerzer kriege ich es einfach nicht mehr:

my @p = (2..100);

while ($i = shift @p) {print $i, ', '; @p = grep {$_ % $i} @p}

Naechste Aufgabe, Sieb des Atkin... *scherz*

Gruss,

Erdbeermarmelade

[Enno]

siehe meine Signatur, 1. Teil!

[bigvic]

Hi,

Kuerzer kriege ich es einfach nicht mehr:

Kuerzer war die Fingerübung ... wie siehts aus mit schneller?

Der Code ist ja sooooo laaaaaaahm

ciao,

victorinox

[bigvic]

Hi,

da fällt mir eben auf ...

my @p = (2..100);

while ($i = shift @p) {print $i, ', '; @p = grep {$_ % $i} @p}

ist kein sieve of Eratosthenes mehr, deshalb ist es auch so lahm.

ciao,

victorinox

[Thomas_xp]

Hallo Leute. Berechnung von Primzahlen geht bei einzelen Prinzahlen schneller ohne das Sieb.

Das Sieb prüft kurz gesagt alle Zahlen, indem es alle Zahlen in einem geählten bereich z.B. 1-10.000 durch 2 teilt, alle die teilbar waren raus schmeißt, und dann mit der nächsten übrig gebliebenen Zahl, also 3, dann 5 etc, weiter macht.

Vorteil: 1) Alle Primzahlen im Bereich 2) Auf dem Papier machbar

Nachteil: rechenintensiv.

Wolltest du also das Sieb probieren.... Wolltest du aber nur eine Zahl auf "primhaftigkeit" prüfen geht das viel schneller. Einfach hochzählen von 2 (n) ab. Damit teilen. Dann innerhalb einer Schleife einfach immer prüfen, ob sich n ohne Rest teilen lässt. Wenn ja, keine Primzahl. Wenn nein einen hoch zählen und weiter (also mit n+1). Und wieder prüfen ob ihne Rest teilbar. So kommst du zu dem Punkt, wo sich eine Zahl durch n ohne Rest teilen lässt. Dann prüfst du noch ob n == Zahl. Wenn ja dann Primzahl. wenn nein (n ist dann automatisch kleiner als Zahl) dann keine Primzahl.

Dies funktioniert bis zum bei int mit Zahlen bis 2 Mrd.-irgenwas. Hier mal der Pseudocode:

int n = 2;

int Zahl;

scanf(Zahl)

while Rest (!= 0)

{

Rest = Zahl%n

n++

}

Wenn Zahl == n dann Primzahl

Else keine Primzahl

ISt super schnell im Vergleich zum SIeb

[beebof]

ISt super schnell im Vergleich zum SIeb

geht noch schneller. Es reicht, wenn du bis zu sqrt(Zahl) hochzählst.

[Wolfs]

hi,

ich weis nicht ob es hier welche gibt die sich noch mit Pascal Auskennen

ich rechne mit dem Sieb alle Primzahlen zwischen 2-400mio innerhalb einer minute und schreibe dabei noch alle Primzahlen die ich finde in externe textdateien ich brauch mehr dateien dar 450MB grosse dateien durch keinen Reader geoffnet werden koennen.

ich benutze 11 dateien dar diese dann jedesmal nur 45 mb gross sind.

das Programm ist im delphi geschrieben.

program Primzahlen;

{$APPTYPE CONSOLE}

uses

SysUtils,

windows;

var All : array [2..400000000] of integer;

I,J,NextPrim,count:integer;

start,stop:tDateTime;

f1,f2,f3,f4,f5,f6,f7,f8,f9,f10,f11:textFile;

begin

{$M 10000000}

J:=2;

start:=Now(); //Zeit starten um zu rechnen wie lange das fuellen dauert

for I:= 2 to 400000000 do //array fuellen mit werten 2-400mio

All:=I;

stop:=now(); //zeit stoppen

writeln('Array mit allen Werten von 2-400.000.000 fuellen dauert -> ',round((stop-start)*86400),'s'); //zeit rausschreiben

start:=Now(); //zeit starten um die zeit des suchens zu berechnen.

NextPrim:=0;

while NextPrim <= round(sqrt(400000000)) do //kucken ob Nextprim nicht ueber 20.000 geht mehr durchgaenge wer ueberfluessig

begin

NextPrim:=0;

while NextPrim=0 do

begin

if All[J]<>0 then //erstbeste Primzahl suchen

NextPrim:=J;

inc(J);

end;

I:=NextPrim; //alle vorherigen moeglichkeiten sind schon getestet

while NextPrim*I<=400000000 do //solange loeschen bis das die nexte zahl ueber 400mio geht

begin

All[NextPrim*I]:=0;

inc(I);

end;

end;

stop:=now(); //zeit Stoppen

writeln('Alle Primzahlen zwischen 2-400.000.000 rechnen dauert -> ',round((stop-start)*86400),'s'); //zeit des berechnens rausschreiben

start:=Now(); //Zeit fuer in dateien zu schreiben

count:=1;

assign(F1,'Prim01 2-2mio.txt');

assign(F2,'Prim02 2mio1-4mio.txt');

assign(F3,'Prim03 4mio1-6mio.txt');

assign(F4,'Prim04 6mio1-8mio.txt');

assign(F5,'Prim05 8mio1-10mio.txt');

assign(F6,'Prim06 10mio1-12mio.txt');

assign(F7,'Prim07 12mio1-14mio.txt');

assign(F8,'Prim08 14mio1-16mio.txt');

assign(F9,'Prim09 16mio1-18mio.txt');

assign(F10,'Prim10 18mio1-20mio.txt');

assign(F11,'Prim11 20mio1-21mio.txt');

rewrite(f1);

rewrite(f2);

rewrite(f3);

rewrite(f4);

rewrite(f5);

rewrite(f6);

rewrite(f7);

rewrite(f8);

rewrite(f9);

rewrite(f10);

rewrite(f11);

for I:= 2 to 400000000 do //alle felder ueberpruefen um in dateien zu schreiben

case Count of

1..2000000: if All<>0 then begin writeln(F1,count,' <= ',All); inc(Count) end;

2000001..4000000: if All<>0 then begin writeln(F2,count,' <= ',All); inc(Count) end;

4000001..6000000: if All<>0 then begin writeln(F3,count,' <= ',All); inc(Count) end;

6000001..8000000: if All<>0 then begin writeln(F4,count,' <= ',All); inc(Count) end;

8000001..10000000: if All<>0 then begin writeln(F5,count,' <= ',All); inc(Count) end;

10000001..12000000: if All<>0 then begin writeln(F6,count,' <= ',All); inc(Count) end;

12000001..14000000: if All<>0 then begin writeln(F7,count,' <= ',All); inc(Count) end;

14000001..16000000: if All<>0 then begin writeln(F8,count,' <= ',All); inc(Count) end;

16000001..18000000: if All<>0 then begin writeln(F9,count,' <= ',All); inc(Count) end;

18000001..20000000: if All<>0 then begin writeln(F10,count,' <= ',All); inc(Count) end;

20000001..22000000: if All<>0 then begin writeln(F11,count,' <= ',All); inc(Count) end;

end;

closeFile(f1);

closeFile(f2);

closeFile(f3);

closeFile(f4);

closeFile(f5);

closeFile(f6);

closeFile(f7);

closeFile(f8);

closeFile(f9);

closeFile(f10);

closefile(f11);

stop:=now(); /zeit stoppen

writeln('Alle Primzahlen zwischen 2-400.000.000 in Dateien zu schreiben dauert -> ',round((stop-start)*86400),'s'); //zeit rausschreiben fuer alle primzahlen in dateien zu schreiben

readln; //damit das programm nicht automatish stoppt.

end.

ich bin anfaenger mach erst 3 Jahre programmation und bin 19 Jahre alt wenn irgendwer eine methode findet wie man dieses Programm schneller kriegt soll er/sie sich melden.

mfg Wolfs

[deano]

das programm sollte schon schneller laufen indem du einmal NextPrim*2 rechnest, dann einmal hochzählst und ab dann bei jedem durchlauf J um zwei erhöhst. da 2 zwei alle geraden zahlen abdeckt, würden 4, 6, 8, ... nur überflüssige operationen durchführen. die ungeraden auch abzudecken ist sehr aufwendig.

edit: rechtschreibung ist auch in kommentaren von quelltexten gerne gesehen

[Ezra]

Das wurde hier zwar schon schnipselweise gesagt (nur bis Wurzel n prüfen und gerade Zahlen rauslassen), aber das ist der Alg, den wir vor einem Jahr in C machen mussten:

unsigned long int n,i;

int ergebnis=1;

printf("Welche Zahl? ");

scanf("%lu",&n);

if(n%2 == 0){

     ergebnis=0;

}else{

     for(i=3;i<=sqrt(n);i+=2){ //testen für alle ungeraden Zahlen kleinergleich Wurzel(n)

              if(n%i==0){

                   ergebnis=0;

              }                         

     }          

}


if(ergebnis==0){ 

     printf("%lu ist keine Primzahl. \n\n", n);

}else{

     printf("%lu ist eine Primzahl. \n\n", n);

}

Bearbeitet 16. Juni 2009 von Ezra