Das berühmteste Verfahren zur Bestimmung von Primzahlen ist das durch den griechischen Mathematiker Eratosthenes von Kyrene, welcher 235 v.u.Z. Vorsteher der Bibliothek in Alexandria wurde, entwickelte Primzahlsieb. Es ermittelt Primzahlen in einem vorgegebenen Intervall, indem alle zusammengesetzten Zahlen ausgesiebt werden:
„… Man denke sich die Folge der natürlichen Zahlen hingeschrieben und streiche, zunächst von 2 ausgehend, jede zweite Zahl, also, 4,6,8,…, dann von 3 ausgehend, jede dritte Zahl, also 6,9,12,…, dann von 5 ausgehend, jede fünfte Zahl, usw… Die 4 wurde als Ausgangszahl übergangen, weil sie als Vielfaches von 2 bereits gestrichen war… Übrig bleiben augenscheinlich nur die Primzahlen…“
„Über Zahlen und Überzahlen“, von Krbek
Dieses Teilprogramm veranschaulicht die Wirkung dieses Verfahrens.
Je nach eingestelltem Startwert werden jeweils 210 Zahlen angezeigt. Entsprechend dem Siebverfahren streicht das Programm sofort zuerst alle durch zwei teilbaren Zahlen (rot), danach alle durch 3 teilbaren (violett), alle durch 5 teilbaren (blau) usw.
Beenden kann man das Verfahren jeweils, wenn das Quadrat der Streichzahl größer als die letzte zu untersuchende Zahl ist. Im Ergebnis bleiben nur Primzahlen als nicht durchgestrichene Zahlen übrig.
Möchten Sie keine farbige Darstellung der gestrichenen Zahlen, so markieren Sie das Feld farbige Darstellung nicht. Am Rollbalken stellen Sie die Größe der ersten Zahl des untersuchten Intervalls ein. Als höchster Wert ist dabei 10 Millionen möglich. Markieren Sie das Feld Streichzahl, trägt das Programm für jedes Feld die Primzahl ein, bei der diese Zahl zuerst gestrichen wurde.
Wählen Sie Zahl ausblenden, so löscht das Programm die zusammengesetzten Zahlen und zeigt nur noch die Primzahlen an.
Möchten Sie das schrittweise Aussieben der zusammengesetzten Zahlen nachvollziehen, so ändern Sie den Rollbalken Streichzahl. Voreingestellt ist alle, d.h., alle Zahlen werden ausgesiebt. Ändern Sie den Wert auf 2, 3 …, werden nur die Zahlen von 2 bis zum eingestellten Wert zum Streichen genutzt. Stellen Sie keine ein, erhalten Sie ausschließlich die Auflistung der zu testenden Zahlen.
Pascaltext zum Sieb des Eratosthenes
Der Quelltext ermöglicht die Berechnung aller Primzahlen bis 1000 mit Hilfe des Siebes des Eratosthenes:
program sieb;
uses crt;
var zahl:array[1..1000] of boolean; i,j,grenze:integer;
begin
grenze:=1000;
fillchar(zahl,sizeof(zahl),true);
i:=2; //erste Streichzahl
repeat
j:=i+i;
repeat
zahl[j]:=false;
j:=j+i; //nächste zu streichende Zahl
until j>grenze;
inc(i);
while zahl[i]=false do inc(i);
until i>sqrt(grenze);
for i:=2 to grenze do
if zahl[i] then write(i:8);
end.
Geschichte des Primzahlsiebs
Das Primzahlsieb des Eratosthenes wurde in der Geschichte mehrfach zum Aufstellen neuer Rekorde genutzt.
Alle Primzahlen im Bereich von 1 bis 10 Millionen wurden durch den US-amerikanischen Mathematiker D.Lehmer berechnet. Außer der Berechnung bedurfte es einer sorgfältigen Nachprüfung und der Herausgabe dieser Tabelle, die 1914 veröffentlicht wurde.
Zwanzig Jahre vor Lehmer stellte ein Autodidakt auf dem Gebiet der Mathematik, der russische Priester I.M.Perwuschin, eine Tabelle der Primzahlen gleichen Umfangs; bis 10 Millionen; auf und übergab sie als Geschenk der Nationalen Akademie der Wissenschaften Russlands. Die Tabellen Perwuschins wurden später im Archiv der Akademie der Wissenschaften der UdSSR im Manuskript aufbewahrt und sind bis in unsere Tage noch nicht veröffentlicht worden.
Eine noch gewaltigere Rechenarbeit vollbrachte der Professor der Prager Universität J.F.Kulik. Er führte die Tabelle der Primzahlen bis zu 100 Millionen fort (6 Bände der Primzahlen und der Teiler der zusammengesetzten Zahlen).
Seit 1867 sind die Tabellen Kuliks im Besitz der Bibliothek der Wiener Akademie der Wissenschaften. Ein Band ist jedoch spurlos verschwunden, und zwar derjenige, der die Zahlen im Bereich von der 13. bis zur 23. Million enthielt.
Der sowjetische Mathematiklehrer W.A.Golubew (Kuwschinowo) arbeitete für die Aufstellung der Tabellen der Primzahlen ein System von „Schablonen“ aus, das die Rechenarbeit vereinfacht und die Möglichkeit von Fehlern fast ausschließt.
Mit Hilfe seiner „Schablonen“ ermittelte W.A.Golubew 1939 die Primfaktoren aller Zahlen der 11. Million und 1941 der 12. Million. Seine Tabellen überbrachte er traditionsgemäß der Akademie der Wissenschaften der UdSSR als Geschenk.