Primzahlen bis einer Milliarde ausgeben
-
Hallo erstmal ich hab die Aufgabe bekommen in c++ die Primzahlen bis einer Milliarde auszugeben. Das hab ich schon mal hinbekommen (also ich geh davon aus dass min=1 und max=eine Milliarde)
#include <iostream> using namespace std; int main() { int x,i,mn,mx; cout<<"Bitte geben Sie den Startwert ein\n"; cin>>mn; cout<<"Bitte geben Sie den Endwert ein\n"; cin>>mx; for (x=mn; x<=mx; x++) { for (i=2; i<x; i++) { if (x%i==0) break; } if (i==x) cout<<x<<"\tist eine Primzahl.\n"; } return 0; }
aber bis es alle ausgegeben hat dauert es 1 Jahr hat mein Lehrer gesagt, und diese Zeit soll ich auf 4 Sekunden optimieren.
Aber ich hab keine Idee wie man das machen könnte...Falls jemand weiß wie es geht bitte ich um Hilfe, den Code kann ich auch komplett umschreiben wenn das mit einem anderen Ansatz besser geht.
-
Mal ein paar ganz offensichtliche Optimierungen.
Es können ab 2 nur ungerade Zahlen prim sein.
Die geraden brauchst du nicht testen.Auch braucht die innere Schleife nicht bis x laufen. Wurzel(x) reicht aus.
Sonst wäre eine Suche nach Primzahlentest wohl angebracht.
-
-
Es gibt einige optimierte Primzahlberechnungen, z.B. nur bis sqrt(x) zu suchen oder aber mittels des Sieb des Eratosthenes - s.a. Primzahltest.
-
Außerdem können ab 3 keine Zahlen mehr vorkommen, die durch 3 teilbar sind. Und ditto ab 5, 7 und 11. Und jede andere Primzahl, die man auf dem Weg findet. Vielleicht kann man damit was machen
-
... und du solltest auf die Ausgabe der Zahlen während der Berechnung verzichten.
-
4 Sekunden? Viel Spaß, ich brauche 8min mit -O3
#include <iostream> #include <vector> #include <fstream> using std::size_t; int main() { std::vector<int> primes; for (auto i = 2; i < 1000000000; ++i) { auto is_prime = true; for (auto p : primes) { if (p*p >/*=*/ i) break; else if (i % p == 0) { is_prime = false; break; } } if (is_prime) primes.push_back(i); } std::ofstream os{"primes.txt"}; if (!os) std::cerr << "Unable to open output file\n"; for (size_t i = 0; i < primes.size(); ++i) { os << primes[i] << ' '; if (i && i % 20 == 0) os << '\n'; } }
Optimierungsbedarf würde mich interessieren!
P.S.: Selbst diese Lib, welche ein Dutzend Quellcodedateien enthält und recht (für mich) komplizierte Berechnungen verwendet, nennt 8 Sekunden als Größenordnung (von wegen 4 Sekunden).
-
Bevor du die Zeit weiter reduzierst, solltest du erstmal dafür sorgen, dass das Programm korrekt ist. 9 ist ja nicht wirklich prim...
-
Hier würde ich vorschlagen, nicht erst auf Korrektheit zu achten, sondern gleich zu ganz was anderem zu greifen. Es wurde im Thread genügend genannt. Damit sind ein paar Sekunden auch realistisch.
-
Stimmt, ich hatte eine Änderung noch vorgenommen und der Test sollte
p*p > i
heißen, danke für den Hinweis.
Nun gut, Probedivision ist also nicht der richtige Weg. Was gibt sieben*sieben? Richtig, feine Primzahlen!
P.S.: Damit wurden aus den Minuten Sekunden: https://prof.beuth-hochschule.de/fileadmin/user/oellrich/eratosthenes.pdf Vielleicht hilft es jemandem.
-
HarteWare schrieb:
P.S.: Damit wurden aus den Minuten Sekunden: https://prof.beuth-hochschule.de/fileadmin/user/oellrich/eratosthenes.pdf Vielleicht hilft es jemandem.
Wie viel Speicher braucht das?
-
hmmmmm schrieb:
HarteWare schrieb:
P.S.: Damit wurden aus den Minuten Sekunden: https://prof.beuth-hochschule.de/fileadmin/user/oellrich/eratosthenes.pdf Vielleicht hilft es jemandem.
Wie viel Speicher braucht das?
Eine Milliarde Bit logischerweise, falls man nicht trickst. Da das nicht viel ist, lohnt es sich nicht, zu tricksen.
-
SeppJ schrieb:
hmmmmm schrieb:
HarteWare schrieb:
P.S.: Damit wurden aus den Minuten Sekunden: https://prof.beuth-hochschule.de/fileadmin/user/oellrich/eratosthenes.pdf Vielleicht hilft es jemandem.
Wie viel Speicher braucht das?
Eine Milliarde Bit logischerweise, falls man nicht trickst. Da das nicht viel ist, lohnt es sich nicht, zu tricksen.
Laut google sind das 125 MiB.
-
125MiB sind doch garnichts. Da hast du doch bei einem kleinen GUI-Programm schon.
-
Ich habe jetzt mit
make_unqiue
mir einbitset
zugelegt, wobei es auch möglich ist einenvector<bool>
zu verwenden (+vom Benutzer vorgegebene Grenze). Ich habe nämlich schnell bemerkt, dass auf dem Stack anscheinend der Speicher ausgeht (Segmentation Fault).Es soll auch möglich sein ab 3 nur noch die ungeraden Zahlen zu testen, damit wäre der Speicherbedarf schonmal halbiert. (War das mit tricksen gemeint?)
-
HarteWare schrieb:
Es soll auch möglich sein ab 3 nur noch die ungeraden Zahlen zu testen, damit wäre der Speicherbedarf schonmal halbiert. (War das mit tricksen gemeint?)
Das ist so ziemlich genau die Idee hinter dem Sieb des Eratosthenes und da spart man eher nichts.
-
@Ethon
Für die geraden Zahlen braucht man gleich gar kein Bit vergeben - natürlich spart das dann Speicher.@HarteWare
Ja, das war mit Tricksen gemeint.
-
Es gibt schnellere Siebe, z.B. das: https://en.wikipedia.org/wiki/Sieve_of_Atkin
und andere Primzahlentests: https://en.wikipedia.org/wiki/Miller–Rabin_primality_testEdit: das neuste Verfahren ist IMHO das hier: https://en.wikipedia.org/wiki/AKS_primality_test
-
Im wikipedia-Artikel zu Atkin ist ein Link zu einer optimierten Version.
Dort steht
http://cr.yp.to/primegen. schrieb:
It generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.
-
Wir sollten hier die Anwendungszwecke unterscheiden. Diese ganzen professionellen Primzahltests sind dazu da, von einer Zahl mit Dröflzigmillionen Stellen zu ermitteln, ob sie prim ist oder nicht. Sie sind eher nicht dazu da, dies systematisch für jede Zahl zwischen 0 und 1 Milliarde zu machen. Die Siebe hingegen sind hingegen genau dazu da. Das ist aber eher eine rein akademische Übung in Optimierung, denn es sind schließlich ohnehin sämtliche kleinen Primzahlen bekannt; 1 Milliarde ist eine lächerlich kleine Obergrenze, wenn es um Primzahlen geht.