Kim Walisch

Sieb des Eratosthenes (EcprimeV1.4) 23.10.2003

1. Eratosthenes

Eratosthenes wurde 276 vor Christus in Kyrene, im heutigen Libyen geboren. Er befasste sich unter anderem mit Mathematik, Geographie, Philosophie und Chronologie. Um 240 v.Ch entdeckte Eratosthenes ein Verfaheren zur Bestimmung von Primzahlen bis zu einer oberen Grenze. Etwa 300 Jahre später überlieferte Nicomachus von Gerasa das Verfahren in seinem Buch „Introductio Arithmeticae“ und gab ihm den Namen „Sieb des Eratosthenes“.

Sieb des Eratosthenes:

Man erstellt eine Liste aller natürlichen Zahlen(größer als 1) bis n und streicht alle Vielfachen der Primzahlen kleiner 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 10^10 zu finden.

2. Programm

Das Programm ‚Ecprime.exe’ sucht Primzahlen mit dem traditionnellen Sieb des Eratosthenes. Das Intervall wird dem Programm als Parameter übergeben, wobei die erste Zahl das Ende und die Zweite den Anfang des Intervalls markiert. Am Ende jedes Rechenvorgangs werden die Anzahl der gefunden Primzahlen, Primzahlzwillinge und die dafür benötigte Zeit angezeigt.

Details und weitere Einstellungsmöglichkeiten stehen in der Hilfe (par: /?)

3. Algorithmus

Das Programm ist in effizientem C/C++ geschrieben.
Der Algorithmus unterscheidet sich von einem konventionellem Test im wesentlichen in zwei Punkten. Der Algorithmus benutzt ein kleines, konstantes Sieb das dem L1 Cache angepasst werden kann. Die Zahlen werden in Bits gespeichert, die Komprimierung habe ich noch durch einen 30 Stempel erhöht, d.h nur Zahlen der Form 30k + 1, 7, 11, 13, 17, 19, 23, 29:

31, 37, 41, 43, 47, 49, 53, 59 //Byte

Weitere Optimierungen sind ein 13# bit Wiederholungsfeld (eliminiert alle Vielfachen von 2,3,5,7,11 und 13) und zwei Funktionen um Primzahlen und Primzahlzwillinge Byte-weise zu zählen.

4. Benchmark

‚Ecprime’ ist schneller als D. J Bernstein’s primegen!
Getestet auf einem Pentium III 550MHZ, Sieve size 15015 bytes.

x	Prims(x)	Twins(x)	Time
10	4	2	0.010 sek
10^2	25	8	0.010 sek
10^3	168	35	0.010 sek
10^4	1229	205	0.010 sek
10^5	9592	1224	0.010 sek
10^6	78498	8169	0.010 sek
10^7	664579	58980	0.030 sek
10^8	5761455	440312	0.200 sek
10^9	50847534	3424506	2.533 sek
10^10	455052511	27412679	38.515 sek

5. Download für Intel C++ 6.0

ecprime.exe.zip (61kB)

Quelltext ecprime.source.zip (19kB)

6. Kontakt

Bei Fragen, Anregungen, Vorschlägen, Kritiken und Bug-Reports schicken Bitte an Kim Walisch eine E-Mail (kim.walisch@gmail.com)

7. Forschung

Primzahlen sind die elementaren Bausteine der natürlichen Zahlen, trotzdem gehören sie zu den willkürlichsten Objekten der Mathematik. Die Funktionen p( x ) und p2( x ) bezeichnen die Primzahlen rsp. die Primzahlzwillinge bis x. Ich habe p( 10^14 ) und p2( 10^14 ) ausgerechnet, die gefundenen Werte stimmen mit denen von Thomas R. Nicely überein.

8. Links

http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html (The Art of Prime Sieving)
http://cr.yp.to/primegen.html (D. J Bernstein, primegen)
http://www.trnicely.net/pi/tabpi.html (table of prime counts)

nach oben