Exemple pratique C 33 - Détermination d'un nombre premier

100 exemples classiques en C

Titre :Déterminer si un nombre est premier.

Analyse du programme :Les nombres premiers, aussi appelés premiers, sont en nombre infini. Un entier naturel supérieur à 1 qui ne peut être divisé par aucun autre entier naturel excepté 1 et lui-même.

Code source du programme :

Exemple

#include<stdio.h> #include<math.h> #define MAX 1000 // Taille maximale du tableau int prime[MAX]; // Tableau pour stocker s'il s'agit d'un nombre premier // Méthode simple pour déterminer si un nombre est premier (force brute) int isPrimeNaive(int n) { if (n <= 1) // Les nombres inférieurs ou égaux à 1 ne sont pas premiers return 0; for (int i = 2; i < n; i++) // Vérifier de 2 à n-1 un par un s'ils divisent n if (n % i == 0) // S'il divise exactement, alors il n'est pas premier return 0; return 1; // Si aucun facteur n'est trouvé, alors il est premier } // Vérification optimisée des nombres premiers : ne vérifier que jusqu'à sqrt(n) et ignorer les nombres pairs int isPrime(int n) { if (n <= 1) // Les nombres inférieurs ou égaux à 1 ne sont pas premiers return 0; if (n == 2) // 2 est premier return 1; if (n % 2 == 0) // Exclure les nombres pairs return 0; int limit = (int)sqrt((double)n); // Il suffit de vérifier jusqu'à sqrt(n) for (int i = 3; i <= limit; i += 2) // Commencer à partir de 3 et ne vérifier que les nombres impairs { if (n % i == 0) // S'il divise exactement, alors il n'est pas premier return 0; } return 1; // A passé tous les tests, n est premier } // Initialisation du crible : créer une table de nombres premiers void sieve() { for (int i = 0; i < MAX; i++) prime[i] = 1; // Supposer que tous les nombres sont premiers prime[0] = prime[1] = 0; // 0 et 1 ne sont pas premiers int limit = (int)sqrt((double)MAX); // Il suffit de vérifier jusqu'à sqrt(MAX) for (int i = 2; i <= limit; i++) // Commencer à 2 et parcourir chaque nombre { if (prime[i]) // Si i est premier { for (int j = i * i; j < MAX; j += i) // Marquer les multiples de i comme non premiers prime[j] = 0; } } } // Déterminer si un nombre est premier à l'aide de la méthode du crible int isPrimeSieve(int n) { return prime[n]; // Retourner directement si cet indice est premier } int main() { sieve(); // Initialiser le crible des nombres premiers // Tester divers nombres pour voir s'ils sont premiers printf("N=%d %d\n", 1, isPrime(1)); // Sortie : 1 n'est pas premier printf("N=%d %d\n", 2, isPrime(2)); // Sortie : 2 est premier printf("N=%d %d\n", 3, isPrime(3)); // Sortie : 3 est premier printf("N=%d %d\n", 4, isPrime(4)); // Sortie : 4 n'est pas premier printf("N=%d %d\n", 7, isPrime(7)); // Sortie : 7 est premier printf("N=%d %d\n", 9, isPrime(9)); // Sortie : 9 n'est pas premier printf("N=%d %d\n", 13, isPrime(13)); // Sortie : 13 est premier printf("N=%d %d\n", 17, isPrime(17)); // Sortie : 17 est premier printf("N=%d %d\n", 100, isPrime(100)); // Sortie : 100 n'est pas premier printf("N=%d %d\n", 23, isPrime(23)); // Sortie : 23 est un nombre premier printf("N=%d %d\n", 1, isPrime(1)); // Sortie : 1 n'est pas premier return 0; }

Le résultat de sortie de l'exemple ci-dessus est (un chiffre final de 1 indique un nombre premier, 0 indique qu'il ne s'agit pas d'un nombre premier) :

N=1 0
N=2 1
N=3 1
N=4 0
N=7 1
N=9 0
N=13 1
N=17 1
N=100 0
N=23 1
N=1 0

100 exemples classiques en C

autres extensions