Optimierte Verison Primzahlenausgabe
-
Hi @all,
ich suche nach einem schnellen Algorithmus für die Berechnung der Primzahlen in C.
Hat dazu schon jemand was gemacht? Ich habe zwar vieles gesehen, man findet auch sehr viel im Inet, aber ich muss sagen, so optimiert sind die Lösungen nicht.Eine Frage noch:
Nebenbei programmiere ich auch ein Algorithmus. Ich möchte, wenn ich eine Primzahl gefunden habe, nicht jedesmal mit einem printf in der Schleife die Zahl ausgeben, sondern möchte die Zahlen erst sammeln und hinterher, wenn die Schleife durchlaufen ist mit einem einzigen printf alle Zahlen ausgeben.
Wie mache ich das am Besten. Ich habe mir überlegt alle Zahlen in einem Array abzuspeichern. Gibt es da bessere Möglichkeiten?MfG
-
Von welchem Bereich reden wir hier? Spielereien bis ein paar Milliarden oder "richtige" Primzahlsuche?
Richtig große Primzahlen suchst du gewöhnlicherweise, indem du einfach zufällig mit einer Zahl anfängst und dann auf diese Zahl und ihre Nachfolger einen schnellen probabilistischen Primzahltest ausführst, bis du eine Primzahl gefunden hast.
Für Spielereien musst du erst einmal die Spielregeln festlegen. Die optimierteste Variante ist wohl einfach ein großes puts mit einer Tabelle aller Primzahlen bis X.
wn12 schrieb:
Eine Frage noch:
Nebenbei programmiere ich auch ein Algorithmus. Ich möchte, wenn ich eine Primzahl gefunden habe, nicht jedesmal mit einem printf in der Schleife die Zahl ausgeben, sondern möchte die Zahlen erst sammeln und hinterher, wenn die Schleife durchlaufen ist mit einem einzigen printf alle Zahlen ausgeben.
Wie mache ich das am Besten. Ich habe mir überlegt alle Zahlen in einem Array abzuspeichern. Gibt es da bessere Möglichkeiten?Lass mich raten: Du glaubst, das wäre schneller? Da muss ich deinen Glauben enttäuschen. Prinzipiell ist es aber möglich, ja. Zum Beispiel über dein Array, wobei du dann den Formatstring dynamisch erzeugen musst. Aber insgesamt ist das Vorhaben zu unsinnig, um sich da großartig Gedanken drüber zu machen.
-
Ooooh sorry,
habe einiges weggelassen :D...
Es soll kein Spiel sein, sondern eine richtige Primzahlsuche in einem Intervall z.B. von 3 - 100 000. Alle Primzahlen sollen nacheinander ausgegeben werden.
-
SeppJ schrieb:
Lass mich raten: Du glaubst, das wäre schneller? Da muss ich deinen Glauben enttäuschen. Prinzipiell ist es aber möglich, ja. Zum Beispiel über dein Array, wobei du dann den Formatstring dynamisch erzeugen musst. Aber insgesamt ist das Vorhaben zu unsinnig, um sich da großartig Gedanken drüber zu machen.
Naja, zumindestens dachte ich, dass es etwas schneller gehen würde. Hab die Überlegung gehabt, alles Zahlen halt in einem Buffer zu schreiben, weil das auslesen von dort aus schneller geht...
-
...
-
Du hast nicht richtig verstanden. 3-100.000 ist bloß ein Spielerei, weil es zu einfach ist. Hier die Powergamerlösung. Als Bonus gibt's auch noch die 2 als Primzahl gratis:
#include <stdio.h> int main() { puts( " 2 3 5 7 11 13 17 19 23\n" " 29 31 37 41 43 47 53 59 61\n" " 67 71 73 79 83 89 97 101 103\n" " 107 109 113 127 131 137 139 149 151\n" " 157 163 167 173 179 181 191 193 197\n" " 199 211 223 227 229 233 239 241 251\n" " 257 263 269 271 277 281 283 293 307\n" // edit: Und so weiter. Anscheinend kommt die Forensoftware nicht mit so // großen Beiträgen zurecht, daher habe ich mal abgeschnitten. " 99289 99317 99347 99349 99367 99371 99377 99391 99397\n" " 99401 99409 99431 99439 99469 99487 99497 99523 99527\n" " 99529 99551 99559 99563 99571 99577 99581 99607 99611\n" " 99623 99643 99661 99667 99679 99689 99707 99709 99713\n" " 99719 99721 99733 99761 99767 99787 99793 99809 99817\n" " 99823 99829 99833 99839 99859 99871 99877 99881 99901\n" " 99907 99923 99929 99961 99971 99989 99991"); return 0; }
-
SneppJ hahahahha,
ok der war gut... Aber ich war schon ernst :D. Für solch eine Lösung brauch ich doch kein Forum :D...
Ich möchte eine optimierte und schnelle Berechnung. BERECHNUNG
-
Du koenntest mal etwas mehr Hintergrund preisgeben. Drueber zeige doch mal bitte was du hast und warum das Primzahlsieb nicht ausreichend ist? Fuer 3-100000 sind alle Implementierungen schnell.
-
Das war kein Scherz. An den Primzahlen 2-100000 gibt es nichts zu berechnen. Die sind bekannt. Daher ist alles nur Spielerei. Eine optimierte Lösung wird optimiert, indem man möglichst viel Wissen über das Problem einfließen lässt. Hier ist die Lösung des Problems schon bekannt, daher kann man diese Lösung vollständig einfließen lassen. Wenn du unbedingt was berechnen möchtest, kannst du ja noch 99991 unter Kenntnis aller vorherigen Zahlen "finden". Oder ganz kreativ: Mittels Metaprogrammierungstechniken (eher etwas für C++, aber ich erwähne es mal), den Compiler einmalig alle Zahlen suchen lassen (zur Compilezeit!).
Aber ich nehme mal an, das willst du alles nicht. Darum habe ich oben nach den Spielregeln gefragt. Da du sie nicht geliefert hast, formuliere ich sie mal in deinem Sinne:
Zur Programmlaufzeit möglichst schnell alle Primzahlen zwischen 0 und X (X kleiner als der halbe Hauptspeicher in Byte) finden und ausgeben. Dabei darf keine Information über bekannte Primzahlen benutzt werden.Dann ist deine Lösung vermutlich das Sieb von Atkin.
http://en.wikipedia.org/wiki/Sieve_of_Atkin
edit: Nein, ist es nicht, weil das Sieb von Atkin auch Vorabinformation über die ersten paar hundert Primzahlen benutzt. Dann eben das antike Sieb des Erastothenes. Über dessen Performance gibt es hier im Forum unzählige Threads. Die interesantesten Erkenntnisse aus diesen Threads sind wohl, dassif (!x) x = 1;ist in der Regel schneller alsx = 1;
2. Ein gepacktes Format (wie der C++ vector<bool> kann deutlich schneller sein als naive Speichertechniken, wenn man dadurch alle Daten in den Prozessorcache bekommt. Aber auch nur dann, ansonsten ist das eher Mist.
Der Rest der Erkenntnisse ist eher trivial.
edit2: Aus Erkenntnis 2 folgt, dass man den Algorithmus auch so gestalten kann, dass man immer nur ein passendes Segment durchsiebt. Das sollte dann noch besser sein.
-
Era
stosthenes -> Eratosthenesmfg
