La fonction suivante (optimisée pour la rapidité) permet de retourner

• 1 si le paramètre N est un nombre premier,
• 0 sinon :

unsigned char isPrime(unsigned int N)
{
    if(N < 2) return 0;
    if(N == 2) return 1;
    if(N % 2 == 0) return 0;
    for(int i=3; (i*i)<=N; i+=2)
        if(N % i == 0 ) return 0;    
    return 1;
}

Code complet

Le code ci-dessous permet d'afficher tous les nombres premiers entre 0 et 100 :

// Online C compiler to run C program online
#include <stdio.h>

// Fonction qui retourne 1 si N est premier
unsigned char isPrime(unsigned int N)
{
    // 0 et 1 ne sont pas premiers
    if(N < 2) return 0;
    // 2 est premier
    if(N == 2) return 1;
    // Tous les nombres divisible par 2 sont premiers
    if(N % 2 == 0) return 0;
    
    // On parcourt tous les diviseurs impairs entre 3 et racine de N
    for(int i=3; (i*i)<=N; i+=2)
        // Si i est un diviseur de N, ce n'est pas un nombre premier
        if(N % i == 0 ) return 0;    
    // S'il n'y a pas de diviseur, c'est un nombre premier    
    return 1;
}

int main() {
    unsigned int i
    // Boucle qui affiche tous les nombres premiers entre 0 et 100
    for (i=0; i<=100; i++)
        if (isPrime(i))  printf("%d ", i);
    return 0;
}

Explication du code :

Le code ci-dessus implémente une fonction en C pour tester si un nombre est premier. La fonction retourne 1 si le nombre est premier et 0 sinon.

Fonction : unsigned char isPrime(unsigned int N)

Détails du code :

1. Prototype de la fonction :

   unsigned char isPrime(unsigned int N)
   

   • Type de retour : unsigned char est utilisé pour retourner un octet (valeur 0 ou 1), où 0 indique que le nombre n'est pas premier, et 1 indique qu'il est premier.
   • Paramètre d'entrée : Le paramètre N est un entier non signé (unsigned int) représentant le nombre à tester.

2. Cas des nombres inférieurs à 2 :

   if(N < 2) return 0;
   

   • Un nombre est premier s'il est supérieur ou égal à 2. Si N est inférieur à 2, la fonction retourne immédiatement 0, car ces nombres (0 et 1) ne sont pas premiers.

3. Cas du nombre 2 :

   if(N == 2) return 1;
   

   • 2 est le plus petit et seul nombre premier pair. Si N est égal à 2, la fonction retourne immédiatement 1, car 2 est un nombre premier.

4. Test de divisibilité par 2 :

   if(N % 2 == 0) return 0;
   

   • Si le nombre N est pair et différent de 2 (ce qui est vérifié précédemment), il n'est pas premier. Ainsi, si N est divisible par 2, la fonction retourne 0.

5. Boucle pour tester les autres diviseurs impairs :

   for(int i=3; (i*i)<=N; i+=2)
       if(N % i == 0) return 0;
   

   • Initialisation : La boucle commence à i = 3 (le plus petit nombre impair après 1) et teste les diviseurs impairs.
   • Condition : La boucle continue tant que i*i <= N, c'est-à-dire tant que i est inférieur ou égal à la racine carrée de N. Cela permet de réduire le nombre de tests. Si N a un diviseur d plus grand que sa racine carrée, alors il aura nécessairement un autre diviseur plus petit.
   • Incrémentation : La variable i est augmentée de 2 à chaque itération (i += 2), ce qui garantit que seuls les diviseurs impairs sont testés (puisque les nombres pairs ont déjà été éliminés).
   • Test de divisibilité : Si N est divisible par un i quelconque (c'est-à-dire si N % i == 0), la fonction retourne immédiatement 0, car cela signifie que N n'est pas premier.

6. Retour de la fonction :

   return 1;
   

   • Si nous avons quitté la boucle, cela signifie qu'il n'y a aucun diviseur, alors N est premier, et la fonction retourne 1.

Résumé de l'algorithme :

• Les nombres inférieurs à 2 ne sont pas premiers.
• 2 est un nombre premier.
• Tous les autres nombres pairs sont exclus.
• Les diviseurs potentiels sont testés jusqu'à la racine carrée de N, uniquement sur les nombres impairs. Si aucun diviseur n'est trouvé, le nombre est premier.