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