Was ist das Sieb des Eratosthenes?

Funktionsweise

Das Sieb des Eratosthenes dient der Ermittlung aller Primzahlen zwischen 2 und einer Obergrenze. Hierbei werden alle Zahlen zwischen 2 und der Obergrenze zunächst als potentielle Primzahlen markiert. Die kleinste potentielle Primzahl (2) muss eine solche sein und wird ausgegeben. Dann werden alle Vielfachen dieser Zahl bis zur Obergrenze durchlaufen und als Nicht-Primzahlen markiert, da sie als Vielfache keine Primzahlen sein können. Im nächsten Schritt wird die zweitkleinste, noch als Primzahl markierte Zahl (3) ausgegeben und deren Vielfache als Nicht-Primzahlen markiert. Dann wird die drittkleinste noch als Primzahl markierte Zahl (5, denn 4 wurde als Vielfaches von 2 bereits als Nicht-Primzahl markiert) ausgegeben, die Vielfachen von 5 markiert etc.
Das Ergebnis ist die Ausgabe aller Primzahlen zwischen 2 und der angegebenen Obergrenze.

public class Sieb {

    private static final int MAX = 100;
    private static boolean[] isPrim = new boolean[MAX];

    private static int[] machArr() {
        int[] arr = new int[MAX];
        for (int i = 2; i <= arr.length; ++i) {
            arr[i-2] = i;
            isPrim[i-2] = i == 2 || i%2 == 1 ? true : false;
        }
        return arr;
    }

    private static ArrayList<Integer> siebe(int[] n) {
        ArrayList<Integer> prim = new ArrayList<Integer>();
        for (int i = 2; i <= MAX; ++i) {
            if (isPrim[i-2]) {
                prim.add(n[i-2]);
                for (int j = i*i; j <= MAX; j += i) {
                    isPrim[j-2] = false;
                }
            }
        }
        return prim;
    }
    
    private static void gibAus(ArrayList<Integer> list) {
        for(int i : list) {
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        gibAus(siebe(machArr()));
    }
}
            
            

Implementierung

Die Klasse Sieb enthält zwei statische Variablen und, neben main(), drei statische Methoden. Die Variable MAX speichert die Obergrenze des zu prüfenden Wertebereichs und isPrim stellt ein boolean-Array der Länge MAX dar, in dem für jeden zu prüfenden Wert gespeichert wird, ob es sich bei diesem um eine Primzahl handelt oder nicht.

machArr()

Die Methode erzeugt ein int-Array, das die zu prüfende Zahlen in einer aufsteigenden Reihe von 2 bis zur in der Variablen MAX abgelegten Obergrenze speichert. Beim Durchlauf des Arrays werden die Werte darin abgelegt und beim jeweiligen Index der zugehörige boolsche Wert in das Hilfsarray isPrim eingetragen. Hierbei werden der kleinste Wert 2 und alle ungeraden Zahlen als potentielle Primzahlen mit true, alle anderen bereis mit false markiert, da gerade Zahlen als Vielfache von 2 keine Primzahlen sein können.

siebe(int[] n)

Die Methode stellt den eigentlichen Sieb-Algorithmus bereit. Ihr wird das numerische Array mit den zu prüfenden Werten, das von machArr() zurückgegeben wird, als Parameter übergeben.
Im Methodenkörper wird zunächst eine leere ArrayList erzeugt, die später alle Primzahlen aufnimmt. In einer Schleife werden alle Werte von 2 bis MAX durchlaufen und die zum jeweiligen Index gehörigen Einträge in isPrim geprüft. Ist der jeweilige Wert des Zahlenarrays dort mit true als Primzahl gekennzeichnet, so wird er in die ArrayList eingetragen. In einer dann folgenden Schleife werden die Vielfachen dieses Wertes in isPrim mit false markiert, sodass die zugehörigen Werte so von der Primzahlsuche ausgeschlossen werden. Nach Abschluss der Durchläufe enthält die ArrayList alle Primzahlen zwischen 2 und MAX und kann zurückgegeben werden.

gibAus(ArrayList <Integer> list)

Die Methode dient der Ausgabe der Primzahlen. Sie durchläuft die übergebene ArrayList und gibt die dort abgelegten Werte auf der Konsole aus.