Deutsche Lernausgabe

Sieb des Eratosthenes in C

Finden Sie Primzahlen bis zu einer Grenze durch Markieren ihrer Vielfachen.

Erstellen Sie ein Kandidatenarray von 0 bis N und schließen Sie 0 und 1 aus. Markieren Sie für jede Primzahl p ihre Vielfachen. Beginnen Sie bei p * p: Kleinere Vielfache haben bereits einen kleineren Faktor.

Neue Markierungen müssen nur für p bis zur Wurzel von N beginnen. Vermeiden Sie bei großen Grenzen einen Überlauf von p * p, etwa durch p <= N / p bei positivem p. Der Puffer muss Position N enthalten.

Das klassische Sieb benötigt O(N) Speicher und ungefähr O(N log log N) Zeit. Testen Sie die Grenzen 0, 1, 2 und einen größeren Wert und passen Sie das Programm bei Bedarf an.

Quellcode

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

void sieve(int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    printf("Primes up to %d:\n", n);
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) printf("%d ", p);
    }
    printf("\n");
}

int main() {
    int n = 50;
    sieve(n);
    return 0;
}

Im Compiler öffnen

Erwartetes Ergebnis

Primes up to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.