Exemple pratique C 33 - Détermination d'un nombre premier
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 0autres extensions