Diese Seite Unterstützt den ScriptLoader
Das Sieb des Erathostenes gibt Primzahlen von 2 bis zu einer beliebigen Grenze aus.
Beim Algorithmus wird eine Zahl ungleich 0 als Primzahl angenommen (am Anfang die 2).
Anschließend werden alle Vielfachen dieser Zahl gestrichen (i.e. auf 0 gesetzt).
Im Fall 2 sind das alle geraden Zahlen (4, 6, 8, 10 usw.).
Die nachfolgende Zahl ist die 3, da diese nicht gestrichen wurde. Dies ist die neue Primzahl und alle weiteren Vielfachen der 3 werden gestrichen. Die nächste (nicht gestrichene Zahl) ist dann die 5.
Die letzte Zahl bzw. dessen Vielfaches die verglichen werden muss, ist die Hälfte der Länge des Arrays. In diesem Fall wäre es 50.
Dieser Vorgang wird mit Folgendem Code ausgeführt:
public class Erathostenes
{
private int[] zahlenfeld;
public void zahlenfeldBelegen (int pLaenge){
zahlenfeld = new int [pLaenge];
for (int i = 0 ;i< zahlenfeld.length;i++){
zahlenfeld[i]=i;
}
}
public void sieb () {
zahlenfeld[1]=0;
for (int i = 2 ; i< zahlenfeld.length/2;i++){
if(zahlenfeld[i]!=0){
for (int j= 2;i*j<zahlenfeld.length;j++){
zahlenfeld[i*j]=0;}
}
}
}
public boolean primtest(int pZahl){
if (zahlenfeld[pZahl]!=0){
return true;}
else return false;
}
public int primcount(int pStart,int pEnde){
int Zaehler=0;
for(int i = pStart; i <pEnde;i++){
if(zahlenfeld[i]!=0){
Zaehler++;
}
}
return Zaehler;
}
public void Ausgabe(){
for (int i = 0 ;i< zahlenfeld.length;i++){
if(zahlenfeld[i]!=0){
System.out.println(zahlenfeld[i]);
}
}
}
}