In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Das Sieb des Eratosthenes ist ein Klassiker unter den algorithmischen Problemen: Du willst alle Primzahlen bis zu einer Zahl n finden.

Bekannt ist es, weil es einen einfachen, aber sehr cleveren Trick zeigt: Statt jede Zahl aufwändig zu prüfen, markierst du systematisch alle Nicht-Primzahlen.

In diesem Artikel lernst du das Prinzip an einem einsteigerfreundlichen Beispiel und setzt es in Java um.

Der Fokus liegt auf Arrays und einer sauberen Markierungsstrategie, damit du dabei auch gleich gute Grundlagen fürs Programmieren trainierst.

 

Problemstellung

Finde alle Primzahlen im Bereich von 2 bis einschließlich n.

  • Eingabe: eine ganze Zahl n (z.B. 30)
  • Ausgabe: alle Primzahlen bis n (z.B. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
  • Regeln: Eine Primzahl ist größer als 1 und nur durch 1 und sich selbst teilbar.

Mini-Beispiel für n = 10:

  1. Starte mit den Zahlen 2..10.
  2. Markiere Vielfache von 2: 4, 6, 8, 10.
  3. Nächste unmarkierte Zahl ist 3, markiere Vielfache von 3: 6, 9.
  4. Übrig bleiben 2, 3, 5, 7 als Primzahlen.

 

Die Idee dahinter

Du legst ein Array an, das für jede Zahl speichert: ist diese Zahl zusammengesetzt (also keine Primzahl)?

Dann gehst du die Zahlen von 2 aufwärts durch. Wenn eine Zahl noch nicht markiert ist, ist sie eine Primzahl. Anschliessend markierst du alle ihre Vielfachen als "nicht prim".

  • false bedeutet: noch nicht als zusammengesetzt markiert (kann prim sein)
  • true bedeutet: markiert (ist keine Primzahl)

Kurze Visualisierung für n = 12 (M = markiert):

  • 2 (prim) - markiere 4, 6, 8, 10, 12
  • 3 (prim) - markiere 6, 9, 12
  • 4 (M)
  • 5 (prim) - markiere 10
  • 6 (M), 7 (prim), 8 (M), 9 (M), 10 (M), 11 (prim), 12 (M)

 

Schritt für Schritt zur Lösung

  1. Array vorbereiten: Erzeuge ein boolean[] der Länge n + 1, damit du direkt per Index auf Zahlen zugreifen kannst.
  2. Grenzen setzen: Wenn n < 2, gibt es keine Primzahlen.
  3. Durchlaufen: Gehe von 2 bis n durch und prüfe: ist marked[i] noch false?
  4. Primzahl gefunden: Wenn nicht markiert, ist i eine Primzahl.
  5. Vielfache markieren: Markiere alle Vielfachen von i als true, damit sie später übersprungen werden.
  6. Ergebnis sammeln: Sammle alle Zahlen, die am Ende nicht markiert sind.

 

Java-Implementierung (Variante A: straightforward)

import java.util.ArrayList; 
import java.util.List;

public class SieveStraightforward {

  public static void main(String[] args) {
    int n = 30;
    List<Integer> primes = sieve(n);

    System.out.println("n = " + n);
    System.out.println("primes = " + primes);
  }

  public static List<Integer> sieve(int n) {
    List<Integer> primes = new ArrayList<>();

    if (n < 2) {
      return primes;
    }

    boolean[] marked = new boolean[n + 1];

    for (int i = 2; i <= n; i++) {
      if (!marked[i]) {
        primes.add(i);
        markMultiples(marked, i, n);
      }
    }

    return primes;
  }

  private static void markMultiples(boolean[] marked, int base, int n) {
    for (int multiple = base * 2; multiple <= n; multiple += base) {
      marked[multiple] = true;
    }
  }
}

Diese Variante ist bewusst direkt: Wenn du eine Primzahl findest, markierst du ab base * 2 alle Vielfachen. Das ist leicht nachzuvollziehen und gut zum Lernen der Grundidee. Durch die Hilfsmethode bleibt der Code übersichtlich. Performance ist okay für kleine bis mittlere n, aber es gibt unnötige Markierungen.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

import java.util.ArrayList; 
import java.util.List;

public class SieveImproved {

  public static void main(String[] args) {
    int n = 30;
    List<Integer> primes = sieve(n);

    System.out.println("n = " + n);
    System.out.println("primes = " + primes);
  }

  public static List<Integer> sieve(int n) {
    List<Integer> primes = new ArrayList<>();

    if (n < 2) {
      return primes;
    }

    boolean[] composite = new boolean[n + 1];

    int limit = (int) Math.sqrt(n);

    for (int i = 2; i <= limit; i++) {
      if (!composite[i]) {
        markFromSquare(composite, i, n);
      }
    }

    for (int i = 2; i <= n; i++) {
      if (!composite[i]) {
        primes.add(i);
      }
    }

    return primes;
  }

  private static void markFromSquare(boolean[] composite, int p, int n) {
    long start = (long) p * p;

    if (start > n) {
      return;
    }

    for (long multiple = start; multiple <= n; multiple += p) {
      composite[(int) multiple] = true;
    }
  }
}

Hier startest du das Markieren bei p * p. Alles darunter hat bereits einen kleineren Teiler und wurde daher früher markiert. Ausserdem läuft die Markierungs-Schleife nur bis zur Wurzel von n, was die Arbeit deutlich reduziert. Durch long beim Start vermeidest du Überlauf, wenn p * p größer wird.

 

Beispiel: Eingabe und Ausgabe

  • Eingabe: n = 10 Ausgabe: [2, 3, 5, 7]
  • Eingabe: n = 2 Ausgabe: [2]
  • Eingabe: n = 1 Ausgabe: []

 

Typische Fehler

  • Off-by-one beim Array: boolean[] marked = new boolean[n] ist falsch, weil du Index n auch brauchst. Richtig ist n + 1.
  • Falscher Start beim Markieren: In Variante A base * 2 vergessen oder mit base starten würde die Primzahl selbst markieren.
  • Abbruchbedingung zu groß/zu klein: In der verbesserten Variante muss die Markierungsbasis nur bis sqrt(n) laufen. Zu weit laufen ist langsamer, zu kurz liefert falsche Ergebnisse.
  • *Überlauf bei `p p:** Bei größerennkannintüberlaufen. Nutze für den Startlong` und caste erst beim Index.
  • Falsche Bedeutung von true/false: Wenn du true als "prim" interpretierst, verdrehst du schnell die Logik. Benenne das Array passend, z.B. composite.
  • Grenzfälle ignorieren: Bei n < 2 muss die Ausgabe leer sein, sonst bekommst du merkwürdige Ergebnisse oder Schleifenfehler.

 

Fazit

Mit dem Sieb des Eratosthenes hast du gelernt, wie man Primzahlen effizient über ein Markierungs-Array findet. Das Problem ist ein gutes Training für Arrays, Schleifen und sauberes Zerlegen in Hilfsmethoden. Du hast ausserdem gesehen, wie eine kleine Änderung der Markierungsstrategie (p * p statt 2 * p) viel Arbeit sparen kann.