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) Linkshttp://de.wikipedia.org/wiki/Sieb_des_Eratostheneshttp://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 |
