Nederlandse leereditie

Zeef van Eratosthenes in C

Vind priemgetallen tot en met N door veelvouden van kandidaten te markeren.

Maak een array van kandidaten van 0 tot en met N en sluit 0 en 1 uit. Markeer voor elk priemgetal p de veelvouden. Begin bij p * p: eerdere veelvouden hebben al een kleinere factor.

Start markeren alleen voor p tot de wortel van N. Voorkom overloop van p * p bij grote grenzen, bijvoorbeeld met p <= N / p voor positieve p. De buffer moet positie N bevatten.

De klassieke zeef gebruikt O(N) geheugen en ongeveer O(N log log N) tijd. Test 0, 1, 2 en een grotere grens en pas het programma waar nodig aan.

Broncode

#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;
}

Openen in de compiler

Verwacht resultaat

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

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.