Édition pédagogique en français

Crible d’Ératosthène en C

Trouvez les nombres premiers jusqu’à une borne en marquant leurs multiples.

Créez un tableau de candidats de 0 à N et excluez 0 et 1. Pour chaque nombre premier p, marquez ses multiples. Commencez à p * p : les multiples inférieurs ont déjà un facteur plus petit.

Il suffit de commencer le marquage pour p jusqu’à la racine de N. Évitez le débordement de p * p pour de grandes bornes, par exemple avec p <= N / p pour p positif. Le tampon doit inclure la position N.

Le crible classique utilise O(N) de mémoire et environ O(N log log N) de temps. Testez les limites 0, 1, 2 et une valeur plus grande, en adaptant le programme si nécessaire.

Code source

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

Ouvrir dans le compilateur

Résultat attendu

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

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.