La détermination des nombres premiers inférieurs à une valeur est un programme classique de l’apprentissage du langage C. L’objectif du programme doit être de déterminer tous les nombres premiers en dessous d’une valeur paramètre. Nous allons voir au travers de cet article comment mettre en place un algorithme qui réalise cette recherche.
Les développements et les tests sont réalisés dans un environnement Windows Seven. Le compilateur gcc de MinGW en version 32 bits. Le programme reçoit en paramètre le nombre limite sur laquelle la recherche est à effectuer. Pour rechercher les nombres premiers entre 1 et 1 000 000, le programme doit être lancé : premier.exe 1000000
Quelques rappels mathématiques
Dans un premier temps, il faut définir ce qu’est un nombre premier. Un nombre premier est un nombre qui n’est divisible par aucun nombre excepté 1 et lui-même.
- 6 peut être décomposé en 6×1 et 2×3 : ce n’est pas en nombre premier
- 13 peut être décomposé uniquement en 13×1 : c’est un nombre premier
- 20 peut être décomposé en 1×20, 2×10, 4×5 : ce n’est pas un nombre premier
- …
Les nombres 0 et 1 ne sont pas premiers.
Le nombre 2 est le seul nombre pair premier puisque tous les autres nombres pairs sont a minima divisibles par 2 donc non premiers.
Recherche basique
La recherche des nombres premiers peut être mise en œuvre par une recherche brute en parcourant tous les nombres compris entre 2 et NOMBRE – 1. Le programme est constitué de 2 boucles imbriquées : la première parcourt tous les nombre entre 2 et NOMBRE et la deuxième recherche pour chaque nombre s’il est divisible par au moins 1 nombre.
#include <stdio.h> #include <stdlib.h> #include <math.h> int main(int argc, char *argv[]) { unsigned long nombreLimite; // Limite de la recherche. Alimenté en paramètre au lancement unsigned long nombreCourant; // Nombre en cours de traitement. Varie entre 2 et nombreLimite unsigned long totalNombresPremiers; // Compteur des nombres premiers trouvés unsigned long i; int estPremier; // Témoin alimenté à 1 si au moins 1 diviseur est trouvé // Alimentation du nombre limite à partir du paramètre nombreLimite = atol(argv[1]); // Initialisation des variables totalNombresPremiers = 0; // Parcourt de tous les nombres entre 2 et nombreLimite pour vérifier // s'ils sont divisibles par au moins un autre nombre for(nombreCourant=2; nombreCourant < nombreLimite; nombreCourant++) { estPremier = 0; // Initialisation du témoin for(i=2; i<nombreCourant; i++) { // Le nombre n'est pas premier car divisible if(nombreCourant % i == 0) { estPremier = 1; // Mise à jour du témoin } } // Si aucun nombre premier n'est trouvé if(estPremier == 0) { totalNombresPremiers++; } } // Affichage du résultat printf("Il y a %lu nombre premiers entre 0 et %lu", totalNombresPremiers, nombreLimite); return EXIT_SUCCESS; } |
Durée de l’exécution pour les nombres premiers entre 0 et 1 000 000 : inconnue, au bout de 30 minutes avec 100% du processeur utilisé j’ai arrêté le test.
Amélioration de l’algorithme
Le temps d’exécution est incroyablement long pour un programme aussi basique, on va essayer d’améliorer l’algorithme pour supprimer les opérations inutiles. Par exemple, il n’est pas utile de tester les nombres pairs puisqu’ils sont tous divisibles par 2 donc non premier. Le nombre 2 qui est le premier nombre premier sera traité comme une exception, et sera directement pris en compte dans le décompte. Le parcours des nombres ne se fera plus en incrémentant de un en un à partir de 2 mais de 2 en 2 à partir de 3 de façon à ne traiter que les nombres impairs.
La définition en termes mathématiques d’un premier est la suivante : un nombre est premier s’il ne possède aucun diviseur premier inférieur ou égal à sa racine carrée. Nous allons voir comment avec cette définition nous allons pouvoir modifier le programme pour améliorer ses performances en réduisant les opérations inutiles. A partir de la définition précédente nous pouvons améliorer le code en :
- Limitant la recherche à la racine carrée du nombre
- Utilisant uniquement les nombres premiers entre 2 et la racine carrée. Ceci implique de devoir stocker les nombres premiers au fur et à mesure qu’ils sont identifiés
- Ne plus contrôler les nombres pairs qui ne sont pas premiers à l’exception de 2. On va pour cela augmenter l’indice de recherche de 2 en 2.
#include <stdio.h> #include <stdlib.h> #include <math.h> int main(int argc, char *argv[]) { unsigned long nombreLimite; // Limite de la recherche. Alimenté en paramètre au lancement unsigned long nombreCourant; // Nombre en cours de traitement. Varie entre 2 et nombreLimite unsigned long totalNombresPremiers; // Compteur des nombres premiers trouvés unsigned long tabPremier[500000]; // Sauvegarde des nombres premiers trouvés unsigned long i; int estPremier; // Témoin alimenté à 1 si au moins 1 diviseur est trouvé // Alimentation du nombre limite à partir du paramètre nombreLimite = atol(argv[1]); // Initialisation des variables : on intègre 2 et 3 directement totalNombresPremiers = 2; tabPremier[0] = 2; tabPremier[1] = 3; // Parcourt de tous les nombres entre 2 et nombreLimite pour vérifier // s'ils sont divisibles par au moins un autre nombre for(nombreCourant=5; nombreCourant < nombreLimite; nombreCourant+=2) { estPremier = 0; // Initialisation du témoin for(i=1; (i<totalNombresPremiers) && tabPremier[i]<(sqrt(nombreCourant) + 1); i++) { // Le nombre n'est pas premier car divisible if((nombreCourant % tabPremier[i]) == 0) { estPremier = 1; // Mise à jour du témoin } } // Si aucun nombre premier n'est trouvé if(estPremier == 0) { tabPremier[totalNombresPremiers] = nombreCourant; totalNombresPremiers++; } } // Affichage du résultat printf("Il y a %lu nombre premiers entre 0 et %lu", totalNombresPremiers, nombreLimite); return EXIT_SUCCESS; } |
Durée de l’exécution pour les nombres premiers entre 0 et 1 000 000 : entre 0,3 et 0,5 seconde.