Écrivez une fonction prime en C qui teste si un nombre est premier en lui cherchant un diviseur. Utilisez cette fonction pour afficher dans l’ordre les 100 premiers nombres premiers.

Voici une fonction en C qui teste si un nombre est premier en lui cherchant un diviseur, ainsi qu’un programme qui utilise cette fonction pour afficher les 100 premiers nombres premiers :

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

// Fonction pour tester si un nombre est premier
bool estPremier(int nombre) {
    if (nombre <= 1) {
        return false;
    }
    for (int i = 2; i * i <= nombre; i++) {
        if (nombre % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int compteur = 0;
    int nombre = 2;

    printf("Les 100 premiers nombres premiers sont :\n");

    while (compteur < 100) {
        if (estPremier(nombre)) {
            printf("%d ", nombre);
            compteur++;
        }
        nombre++;
    }

    return 0;
}

Explication du code :

1. Fonction estPremier :

   • Cette fonction prend un entier nombre en entrée et retourne true si le nombre est premier, sinon false.
   • Un nombre est considéré comme premier s’il est supérieur à 1 et n’a pas de diviseurs autres que 1 et lui-même.
   • La boucle for vérifie les diviseurs potentiels de 2 à la racine carrée du nombre (i * i <= nombre). Si un diviseur est trouvé, le nombre n’est pas premier.

2. Fonction main :

   • Initialise un compteur compteur à 0 pour suivre le nombre de nombres premiers trouvés.
   • Initialise nombre à 2, le premier nombre premier.
   • Utilise une boucle while pour trouver les 100 premiers nombres premiers.
   • Si estPremier(nombre) retourne true, le nombre est affiché et le compteur est incrémenté.
   • Incrémente nombre à chaque itération pour vérifier le nombre suivant.

Compilation et exécution :

Pour compiler et exécuter ce programme, vous pouvez utiliser un compilateur C comme gcc :

gcc -o premiers_nombres_premiers premiers_nombres_premiers.c
./premiers_nombres_premiers

Cela affichera les 100 premiers nombres premiers dans l’ordre.

Pourquoi arrêter la boucle avec i*i<=nombre ? Quel est le lien avec la racine carrée ?

La condition i * i <= nombre dans la boucle for est utilisée pour optimiser la recherche des diviseurs d’un nombre. Voici pourquoi cette condition est liée à la racine carrée du nombre :

Explication :

1. Diviseurs d’un nombre :

   • Si un nombre n a un diviseur d (où d est un entier), alors n a également un diviseur n/d.
   • Par exemple, si n = 36 et d = 4, alors 36/4 = 9, ce qui signifie que 36 a les diviseurs 4 et 9.

2. Racine carrée :

   • Pour un nombre n, si d est un diviseur de n et d ≤ √n, alors n/d ≥ √n.
   • Cela signifie que tous les diviseurs de n peuvent être trouvés en vérifiant seulement les nombres jusqu’à √n.

3. Optimisation :

   • En vérifiant les diviseurs potentiels jusqu’à √n, on réduit considérablement le nombre d’itérations nécessaires.
   • Par exemple, pour n = 100, au lieu de vérifier tous les nombres de 2 à 99, il suffit de vérifier les nombres de 2 à 10 (puisque √100 = 10).

Condition i * i <= nombre :

• La condition i * i <= nombre est équivalente à i ≤ √n.
• Utiliser i * i évite le calcul explicite de la racine carrée, ce qui peut être légèrement plus efficace en termes de performance.
• Si i dépasse √n, alors i * i dépassera n, et il n’est plus nécessaire de continuer la boucle.

Exemple :

Pour le nombre 36 :

• La racine carrée de 36 est 6.
• Les diviseurs potentiels à vérifier sont donc 2, 3, 4, 5, et 6.
• Si aucun de ces nombres ne divise 36 (ce qui n’est pas le cas ici, puisque 36 est divisible par 2, 3, 4, et 6), alors 36 serait premier.

En résumé, la condition i * i <= nombre permet de limiter la recherche des diviseurs aux nombres jusqu’à la racine carrée du nombre, ce qui est une optimisation importante pour déterminer si un nombre est premier.

Dans la fonction estPremier, pourquoi le if n’a pas de else, et pourquoi le return true se trouve placé après la boucle plutôt que dedans ?

Dans la fonction estPremier, la structure du code avec le if sans else et le return true placé après la boucle est conçue pour optimiser la vérification de la primalité d’un nombre. Voici pourquoi cette structure est utilisée :

Explication :

1. Vérification des diviseurs :

   • La boucle for parcourt les nombres de 2 à la racine carrée du nombre (i * i <= nombre).
   • Si un diviseur est trouvé (c’est-à-dire si nombre % i == 0), le nombre n’est pas premier, et la fonction retourne immédiatement false.

2. Absence de else :

   • Le if à l’intérieur de la boucle vérifie si le nombre est divisible par i. Si c’est le cas, la fonction retourne false et sort immédiatement.
   • Il n’y a pas besoin d’un else ici parce que si un diviseur est trouvé, la fonction se termine immédiatement avec return false.
   • Si aucun diviseur n’est trouvé pendant toute la durée de la boucle, cela signifie que le nombre est premier.

3. Placement de return true :

   • Le return true est placé après la boucle parce que si la boucle se termine sans trouver de diviseur, cela signifie que le nombre est premier.
   • Si la boucle parcourt tous les nombres jusqu’à la racine carrée du nombre sans trouver de diviseur, alors le nombre est premier, et la fonction retourne true.

Code avec commentaires :

bool estPremier(int nombre) {
    if (nombre <= 1) {
        return false; // Les nombres <= 1 ne sont pas premiers
    }
    for (int i = 2; i * i <= nombre; i++) {
        if (nombre % i == 0) {
            return false; // Si un diviseur est trouvé, le nombre n'est pas premier
        }
    }
    return true; // Si aucun diviseur n'est trouvé, le nombre est premier
}

Exemple de fonctionnement :

• Pour nombre = 11 :

  • La boucle vérifie les diviseurs potentiels 2 et 3 (puisque √11 ≃ 3.3).
  • 11 n’est divisible ni par 2 ni par 3.
  • La boucle se termine sans trouver de diviseur, donc la fonction retourne true.

• Pour nombre = 12 :

  • La boucle vérifie les diviseurs potentiels 2 et 3 (puisque √11 ≃ 3.5).
  • 12 est divisible par 2.
  • La fonction retourne false dès que le diviseur 2 est trouvé, sans vérifier les autres nombres.

En résumé, cette structure permet de sortir de la fonction dès qu’un diviseur est trouvé, ce qui est plus efficace. Le return true est placé après la boucle pour indiquer que le nombre est premier seulement si aucun diviseur n’a été trouvé.

Dans le main, pourquoi utiliser une boucle while plutôt qu’une boucle for alors qu’on sait qu’on veut aller jusqu’à compteur == 100 ?

Dans le programme, une boucle while est utilisée pour trouver les 100 premiers nombres premiers. Bien que l’on sache que l’on veut aller jusqu’à ce que compteur soit égal à 100, l’utilisation d’une boucle while est appropriée dans ce contexte pour plusieurs raisons. Voici pourquoi :

Explication :

1. Condition de terminaison basée sur le compteur :

   • La boucle while continue tant que compteur est inférieur à 100. Cela signifie que la boucle s’exécutera jusqu’à ce que 100 nombres premiers aient été trouvés.
   • Une boucle for est généralement utilisée lorsque le nombre d’itérations est connu à l’avance. Dans ce cas, nous ne savons pas à l’avance combien de nombres nous devons vérifier pour trouver 100 nombres premiers.

2. Incrémentation conditionnelle :

   • À chaque itération, le programme vérifie si le nombre actuel est premier. Si c’est le cas, le compteur est incrémenté.
   • Si une boucle for était utilisée avec une condition basée sur compteur, il serait plus complexe de gérer l’incrémentation conditionnelle du compteur.

3. Simplicité et lisibilité :

   • La boucle while rend le code plus lisible et plus simple à comprendre. La condition compteur < 100 est directement liée à l’objectif de trouver 100 nombres premiers.
   • Une boucle for nécessiterait une gestion plus complexe de l’incrémentation du compteur et de la vérification des nombres premiers.

Code avec commentaires :

int main() {
    int compteur = 0; // Compteur pour le nombre de nombres premiers trouvés
    int nombre = 2;   // Le premier nombre à vérifier

    printf("Les 100 premiers nombres premiers sont :\n");

    while (compteur < 100) { // Continuer jusqu'à ce que 100 nombres premiers soient trouvés
        if (estPremier(nombre)) { // Vérifier si le nombre est premier
            printf("%d ", nombre); // Afficher le nombre premier
            compteur++;            // Incrémenter le compteur
        }
        nombre++; // Passer au nombre suivant
    }

    return 0;
}

Comparaison avec une boucle for :

Si l’on essayait d’utiliser une boucle for, cela pourrait ressembler à ceci :

int main() {
    int compteur = 0;
    int nombre = 2;

    printf("Les 100 premiers nombres premiers sont :\n");

    for (; compteur < 100; nombre++) {
        if (estPremier(nombre)) {
            printf("%d ", nombre);
            compteur++;
        }
    }

    return 0;
}

Cependant, cette version avec une boucle for est moins intuitive et peut prêter à confusion, car la condition de terminaison (compteur < 100) et l’incrémentation (nombre++) ne sont pas directement liées dans la déclaration de la boucle.

En résumé, l’utilisation d’une boucle while dans ce contexte est plus appropriée car elle permet de gérer facilement la condition de terminaison basée sur le compteur de nombres premiers trouvés, tout en maintenant la simplicité et la lisibilité du code.