Falls es jemanden interessiert: Ich den 'Sieve of Atkins' aus der PrimeGen-Library in Delphi übersetzt. Die Version findet alle Primzahlen bis 500.000.000 in 850ms, gemessen auf einem Pentium 4 M 1.5 Ghz.

Im Anhang: Kleines Testprogramm und Verfahren, einfach mal nach "PrimeGen" googeln.

Hallo,

ich bin bei diesem Programm etwas ueber die Anzahl der Primzahlen erstaunt, da diese meiner Meinung nach zu gross ist.
800 Mhz Duron:

1: Time = 2232
2: Time = 2448
3: Time = 2458
4: Time = 2434
5: Time = 2365
6: Time = 2315
7: Time = 2240
8: Time = 2598
9: Time = 2773
10: Time = 2875
29595801 primes up to 500660190 in 2474 tics

Mein Programm von www.softgames.de/for...t=20789&start=30 für Turbo Pascal stimmt mit den Daten von did.mat.uni-bayreuth...Seminar/HTML/pz5.htm ueberein.


ERATOSTHENES SIEB bis: 1000000000

Es sind 50847534 Primzahlen bis 1000000000

Es dauerte 1835 100.stel Sekunden
Fertig mit Zahl<Enter>
Aber ich erhalte viel weniger Primzahlen.
ERATOSTHENES SIEB bis: 500660190

Es sind 26388846 Primzahlen bis 500660190

Es dauerte 967 100.stel Sekunden
Fertig mit Zahl<Enter>

29595801 primes up to 500660190 in 2474 tics
Es sind 26388846 Primzahlen bis 500660190

Da liegen 3 Mio Zahlen dazwischen (mehr als 10%)!

Da bedarf es einiger Korrekturen.

Gruss Horst

EDIT Softgames hat sich verkürzt.

Das was Horst_H sagt stimmt, ich habe das eben mal mit dem originalen ecprime überprüft -> Es sind 26388846 Primzahlen bis 500660190

mfg

Hallo,

falls Du es gesehen hast, gibt es ein Wiederholungsfeld, indem alle Vielfachen von 2,3,5,7,11,13 schon ausgestrichen sind
Den Stempel gibt es auch hier
Ältere Version
www.qsl.net/w2gl/blackkey.html

Gruss Horst
P.S.:
Ich habe eben mal
www.delphi-forum.de/download.php?id=1201
PrimFinder.zip
.. Bei mir(=Phantom1) braucht dieses Programm 2930ms....
ausgeführt und der braucht auch 8,07 sec, ist also nur 19% schneller als meine Uraltversion fuer Turbo Pascal.
Ich hatte vermutet, die Kompression der Daten von 30 Byte auf 1 byte haette groessere Auswirkungen.

EDIT:
Anbei ein Programm, was qsl.net in etwa nachahmte, aber einen kompletten Bereich abklappert, statt kurze, cache-freundliche Abschnitte.
Es funktioniert bis 82e9 bei Belegung von fast 2 Gbyte ( 1300 Sekunden) , unter Auslassung aller Vielfacher von 2,3,5,7,11,13.
Wenn man 17 auch noch weglässt funktioniert es bis 86e9 wird aber noch langsamer.Da nichts mehr ( Zahlen-feld) in den Level I Cache passt

Edit..: devalco ist jetzt anders verlinkt

Mann, seit ihr pingelig! Die paar Primzahlen extra, was wollt ihr überhaupt? Die sind umsonst! Persönliche Zugabe!
Im Ernst: In der inneren Schleife ist das "inc (k,q)" beim Optimieren eine Zeile hochgerutscht. Jetzt stimmts.

alzaimar hat folgendes geschrieben:

Mann, seit ihr pingelig! Die paar Primzahlen extra, was wollt ihr überhaupt? Die sind umsonst! Persönliche Zugabe! Im Ernst: In der inneren Schleife ist das "inc (k,q)" beim Optimieren eine Zeile hochgerutscht. Jetzt stimmts.

Durch diese "Kleinigkeit" braucht der Code jetzt 1312ms anstatt 726ms

mfg

Er rechnet doch auch die doppelte Anzahl von Primzahlen aus, oder?

Hallo,

jau , und es läuft auch in nicht einmal der doppelten Zeit bei mir (ca. 4,1 sec).
Jetzt fehlt nur noch eine Kleinigkeit, um bei der richtigen Zahl zu stoppen und nicht so merkwürdig krummen Zahlen.

Gruss Horst

Hi Horst,

da fehlt noch Einiges. Ich wollte eigentlich nur mal so eine Anregung geben. negaH meinte (zu Recht), es gäbe außer seiner Implementierung keine andere in Delphi. Da es auch um Performance ging, dachte ich mir, ich schnapp mir mal den PrimeGen. Und siehe da: Das richtige Verfahren ist wichtig!

Da jedoch negaH und Phantom1 (Du vermutlich auch) die Primzahleggschbedde sin, halte ich mich da raus. Es bringt nix, wenn ich mit meinen 3% Wissen über Primzahlen da mitmische...

Ich fände es unpässlich, den Primgen zu nehmen, in Delphi abzutippen und dann irgendwie meinen Namen damit in Verbindung zu bringen. Wie wäre es, wenn Du Dir den Sourcecode von PrimeGen schnappst (googel nach 'Bernstein PrimeGen') und in Delphi trommelst. Das ist ja alles Hausmannskost, man muss ja nix mehr selbst entwickeln.

Danke trotzdem für die Fehlererkennung und die Anmerkungen!

Ach, Du müsstest eigentlich nur in der Funktion "Count" an der richtigen Stelle rausspringen, so schwer ist das nicht. Wenn man das Verfahren kapiert hat. Hab ich aber nicht. Die "merkwürdig krummen Zahlen" liegen daran, das immer so ein Block knapp unter 1Mio Zahlen durchrechnet, da kommt zu Schluss eben sowas raus...

Gruss aus Berlin

Bin mir bewußt, dass dieses Topic bereits lange überholt ist...
Dennoch mein Senf dazu für alle, die mal einen Primzahltest programmieren wollen...
Hatte in letzter Zeit einige Vorlesungen über dieses Thema - in Mathematikprogrammen (Matlab, Derive, MathCat, Maple, ...) wird das so gehandhabt, daß bis zu einer gewissen Zahl (z.B. 1024=2^10, 1048576=2^20) alle kleineren Primzahlen verwendet, um zu schauen, ob das zu testende x ein Vielfaches davon ist.
Ist dies nicht der Fall, werden NICHT alle weiteren Primzahlen (und schon gar nicht alle ungeraden kleineren Zahlen) herangezogen, sondern es werden Primzahltests (da gibt es einige - bei Interesse einfach googlen) durchgeführt. Dabei werden zufällig Zahlen generiert, mit denen man dann einiges überprüft - z.B. ob Potenzen von x bestimmte Bedingungen erfüllen.
Durch jede solche Zahl, bei der x nicht als Nicht-Primzahl erkannt wird, halbiert sich die Wahrscheinlichkeit, daß x keine Primzahl ist. Man führt dann also z.B. mit 20 Zahlen diesen Test durch und kann dann sagen: x ist mit Wahrscheinlichkeit >99.9999 keine Primzahl.
Grüße
Stephan

Und so schliesst sich der Kreis
www.delphipraxis.net...c63109,0,asc,15.html

Für alle, die ihre Verfahren testen wollen - hier ein paar meiner Lieblingsprimzahlen:

1248168421 - Man beachte, daß das 2-er Potenzen sind: 1-2-4-8-16-8-4-2-1
1111111111111111111 - sind 19 1-er
11111111111111111111111 - sind 23 1-er
12345678910987654321 - Erklärt sich von selbst: 1-2-3-4-5-6-7-8-9-10-9-8-7-6-5-4-3-2-1
19841407 - Mein Geburtsdatum, YYYYDDMM - 1984-14-07


Viel Spaß beim Testen

Also mit dem Sieb des Erathostenes habe ich 1.000.000 Zahlen in 3:27 Minuten

Dann haste irgendwas falsch gemacht, denn ich brauche für 200.000.000 Zahlen (200x mehr) nur 7,44 Sekunden.

Hallo,

bitte etwas mehr lesen sonst dreht man sich im Kreis.
alzaimer s Sieb nach Atkins ist erheblich schneller. Ca. 4 sec fuer Primzahlen bis 1e9 , mein Programm fuer Turbo pascal 18.75 sec. Das sind 50,8 Mio Zahlen.

Gruss Horst
P.S.: 800 Mhz Duron.

Ich hab ja auch von meiner "Sieb d. E."-Funktion geredet.

zeigt er dir die auch alle an? @GTA

Sieht so aus, ja.

Hier gabs mal die Diskussion darüber, wie viele Primzahlen es gibt:
Für eine Zahl 'n' sei p(n) die Anzahl der Primzahlen, die kleiner oder gleich 'n' sind.
Dann gilt - wens interessiert, bewiesen von Tchebyscheff (~1850) - folgende Aussage:
0.922 < (n/ln(n)) / p(n) < 1.106
Das heißt:

n
----
ln(n)

weicht von der Anzahl der Primzahlen, die kleiner als n sind, um weniger als 10% ab - umso größer die Zahl n ist, desto genauer wird übrigens die Näherung
zB. gibt es unter n=10^6 in etwa 72 382 Primzahlen (+/- 10%, dh. zwischen 66 736 und 80 021)
und das bereits erwähnte Beispiel mit n=500 660 190: Da gibts zwischen 23 044 211 und 27 631 808Primzahlen - dh. die gepostete 29 595 801 kann nicht ganz stimmen, die 26 388 846 hingegen schon