Informatik
Primzahlen mit dem Sieb des Eratosthenes
Gesucht sind alle Primzahlen, die kleiner als eine bestimmte Zahl n sind, also z.B. kleiner als n = 30. Das Sieb des Eratosthenes
ist quasi ein Ausschlussverfahren: Alle Vielfachen von Zahlen fallen durch das Sieb. Zurück bleiben die Primzahlen.
Idee
Zunächst werden alle Zahlen von 2 bis n-1 sozusagen auf Verdacht, bis zum Beweis des Gegenteils, als prim gekennzeichnet. In Bild 1 ist dies durch ein leeres Feld unterhalb der jeweiligen Zahl dargestellt – die Zahlen haben sozusagen zu Beginn noch alle eine weiße Weste. Die Zahlen 0 und 1 werden nicht mit einbezogen.
Bild 1: Initialisierung
Dann wird bei der Zahl 2 begonnen, und es werden alle Vielfachen von 2 gestrichen. In Bild 2 sind diese Zahlen durch ein X gekennzeichnet, denn sie sind nun als doch nicht prim identifiziert.
Bild 2: Vielfache von 2 gestrichen
Fortgefahren wird mit der nächsten Zahl, die als prim gekennzeichnet ist, die also sozusagen noch eine weiße Weste hat, dies ist die 3. Jetzt werden alle Vielfachen von 3 gestrichen. Hierbei kann bei 3·3 = 9 begonnen werden, denn 2·3 = 6 ist als Vielfaches von 2 schon gestrichen (Bild 3).
Bild 3: Vielfache von 3 gestrichen
Weiter fortgefahren wird mit der nächsten Zahl, die noch eine weiße Weste hat, dies ist die 5, und es werden alle Vielfachen von 5 gestrichen. Hierbei kann bei 5·5 = 25 begonnen werden, denn 2·5 = 10, 3·5 = 15, 4·5 = 20 sind als Vielfache von 2 bzw. 3 schon gestrichen.
Das Ganze wird für alle Zahlen bis n-1 fortgesetzt.
Jedes Mal, wenn eine als prim gekennzeichnete Zahl angetroffen wird, wird diese in eine Arrayliste primes eingetragen.
Implementierung
Für die Kennzeichnung der Zahlen wird ein boolesches Array isprime der Länge n verwendet. Eine Zahl i gilt als prim gekennzeichnet, wenn isprime[i] = true ist (2 ≤ i < n).
Das Array isprime wird zu Anfang mit true initialisiert.
In den Bildern 1, 2 und 3 ist dieses Array jeweils dargestellt: Array-Einträge mit dem Wert true entsprechen leeren Feldern, Array-Einträge mit dem Wert false entsprechen durchgekreuzten Feldern. Die Array-Einträge an den Indexpositionen 0 und 1 werden nicht benutzt.
Ab i = 
n werden keine Vielfachen mehr gestrichen, da dann stets j = i·i ≥ n ist. Dann werden nur noch die verbleibenden als prim gekennzeichneten Zahlen in die Arrayliste primes eingetragen.
Zum Schluss enthält die Arrayliste primes alle Primzahlen, die kleiner als n sind.
Es folgt das Programm in der Programmiersprache Java.
{
public static void main(String[] args)
{
ArrayList<Integer> primes=listOfPrimes(30);
for (int p : primes)
System.out.print(p+" ");
System.out.println();
}
// liefert die Liste aller Primzahlen < n
public static ArrayList<Integer> listOfPrimes(int n)
{
ArrayList<Integer> primes=new ArrayList<Integer>();
boolean[] isprime=new boolean[n];
// Array initialisieren
for (int i=2; i<n; i++)
isprime[i]=true;
// Array durchlaufen
for (int i=2; i<n; i++)
if (isprime[i])
{
primes.add(i);
// Vielfache von i streichen
for (int j=i*i; j<n; j+=i)
isprime[j]=false;
}
return primes;
}
}
In der Programmiersprache Python entspricht folgendes Programm dem angegebenen Verfahren.
# Liste der Primzahlen initialisieren
primes=[]
# Sieb initialisieren
isprime=n*[True]
# Sieb durchlaufen
for i in range(2, n):
if isprime[i]:
primes+=[i]
# Vielfache von i streichen
for j in range(i*i, n, i):
isprime[j]=False
return primes
if __name__=="__main__":
print listOfPrimes(30)
Weiter mit: [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 24.11.2019 Updated: 12.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden