Primzahlen bis einer Milliarde ausgeben
-
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_unqiuemir einbitsetzugelegt, 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.
