Inhaltsverzeichnis

Development of
Algorithmic Constructions

13:30:04
Deutsch
19.Sep 2021

Sieb des Eratosthenes:

Man erstellt eine Liste aller natürlichen Zahlen (größer als 1) bis n und streicht alle Vielfachen der Primzahlen größer oder gleich der Quadratwurzel von n durch.
Die verbliebenen Zahlen sind Primzahlen. Das Sieb des Eratosthenes und das davon abgeleitete Sieb von Atkin sind bis heute die schnellsten Methoden um alle Primzahlen bis circa 2^64 zu finden.

Eine Implementation in Cpp mit Heap-Verwaltung und bitweise genutztes Helparray findet man :
kompelierbare Version
(80 min für alle Primzahlen < 10^12)

Links

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://www.faust.fr.bw.schule.de/mhb/eratosib.htm
http://www.primzahlen.de/files/theorie/sieb.htm
http://www.primzahlen.de/files/referent/kw/sieb.htm
http://www.jjam.de/Java/Applets/Primzahlen/Eratosthenes.html