Implémenter le crible d'Ératosthène en C

Introduction

Dans ce laboratoire, vous allez apprendre à implémenter l'algorithme du crible d'Ératosthène en C pour trouver les nombres premiers jusqu'à une limite supérieure donnée. Vous commencerez par lire la limite supérieure à partir de l'utilisateur, puis marquer les multiples des nombres premiers comme non premiers, et enfin imprimer tous les nombres premiers trouvés. Ce laboratoire couvre des concepts de théorie des nombres et de mathématiques discrètes en utilisant le langage de programmation C.

Le laboratoire se compose de trois étapes principales : lire la limite supérieure, marquer les multiples comme non premiers et imprimer tous les nombres premiers. En suivant ces étapes, vous obtiendrez une compréhension plus approfondie de l'algorithme du crible d'Ératosthène et de son implantation en C.

Skills Graph

Lire la limite supérieure

Dans cette étape, vous allez apprendre à lire la limite supérieure pour l'algorithme du crible d'Ératosthène en C. La limite supérieure détermine la plage de nombres premiers que nous voulons trouver.

Tout d'abord, créons un nouveau fichier C pour notre implémentation :

cd ~/projet
nano prime_sieve.c

Maintenant, écrivons le code initial pour lire la limite supérieure :

#include <stdio.h>

int main() {
    int upper_limit;

    printf("Entrez la limite supérieure pour trouver les nombres premiers : ");
    scanf("%d", &upper_limit);

    printf("Limite supérieure entrée : %d\n", upper_limit);

    return 0;
}

Compilez et exécutez le programme :

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Sortie exemple :

Entrez la limite supérieure pour trouver les nombres premiers : 50
Limite supérieure entrée : 50

Analysons le code :

• Nous utilisons scanf() pour lire une entrée entière de l'utilisateur
• Le spécificateur de format %d indique à scanf() de lire un entier
• Nous stockons l'entrée dans la variable upper_limit
• Nous imprimons ensuite la limite supérieure entrée pour confirmer l'entrée

Marquer les multiples comme non premiers

Dans cette étape, vous allez implémenter la logique centrale de l'algorithme du crible d'Ératosthène pour marquer les multiples des nombres premiers comme non premiers.

Modifions le fichier prime_sieve.c précédent :

cd ~/projet
nano prime_sieve.c

Mettez à jour le code pour inclure un tableau et marquer les multiples :

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

int main() {
    int upper_limit;

    printf("Entrez la limite supérieure pour trouver les nombres premiers : ");
    scanf("%d", &upper_limit);

    // Créez un tableau booléen pour marquer les nombres premiers et non premiers
    bool is_prime[upper_limit + 1];

    // Initialisez tous les nombres comme premiers
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Marquez les multiples de chaque nombre premier comme non premiers
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Marquez les multiples de p comme non premiers
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("Le marquage des multiples est terminé.\n");

    return 0;
}

Compilez et exécutez le programme :

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Sortie exemple :

Entrez la limite supérieure pour trouver les nombres premiers : 50
Le marquage des multiples est terminé.

Analysons la logique du crible d'Ératosthène :

• Nous créons un tableau booléen is_prime pour suivre les nombres premiers et non premiers
• Initialement, tous les nombres sont marqués comme premiers
• Nous parcourons les nombres de 2 à sqrt(upper_limit)
• Pour chaque nombre premier, nous marquons ses multiples comme non premiers
• Nous commençons à marquer à partir de p^2 pour optimiser l'algorithme
• La boucle interne incrémente de p pour marquer tous les multiples de p

Afficher tous les nombres premiers

Dans cette étape, vous terminerez l'implémentation du crible d'Ératosthène en affichant tous les nombres premiers trouvés dans la plage donnée.

Modifions le fichier prime_sieve.c pour ajouter la fonctionnalité d'affichage :

cd ~/projet
nano prime_sieve.c

Mettez à jour le code pour afficher les nombres premiers :

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

int main() {
    int upper_limit;

    printf("Entrez la limite supérieure pour trouver les nombres premiers : ");
    scanf("%d", &upper_limit);

    // Créez un tableau booléen pour marquer les nombres premiers et non premiers
    bool is_prime[upper_limit + 1];

    // Initialisez tous les nombres comme premiers
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // Marquez les multiples de chaque nombre premier comme non premiers
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // Marquez les multiples de p comme non premiers
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // Affichez tous les nombres premiers
    printf("Les nombres premiers jusqu'à %d sont :\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

Compilez et exécutez le programme :

gcc prime_sieve.c -o prime_sieve
./prime_sieve

Sortie exemple :

Entrez la limite supérieure pour trouver les nombres premiers : 50
Les nombres premiers jusqu'à 50 sont :
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Analysons les dernières étapes :

• Après avoir marqué les multiples, nous parcourons le tableau is_prime
• Nous affichons seulement les nombres qui restent marqués comme premiers
• La sortie montre tous les nombres premiers jusqu'à la limite spécifiée par l'utilisateur

Résumé

Dans ce laboratoire, vous avez d'abord appris à lire la limite supérieure pour l'algorithme du crible d'Ératosthène en C. Vous avez créé un fichier C, prime_sieve.c, et écrit du code pour demander à l'utilisateur la limite supérieure et la stocker dans la variable upper_limit. Ensuite, vous avez implémenté la logique centrale de l'algorithme du crible d'Ératosthène en créant un tableau booléen pour marquer les nombres premiers et non premiers. Vous avez initialisé tous les nombres comme premiers puis marqué les multiples de chaque nombre premier comme non premiers. Enfin, vous allez apprendre à afficher tous les nombres premiers dans la limite supérieure donnée.