Nombres premiers en C

Share Button

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

Nombres premiers en C

Programme de recherche des nombres premiers en C

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.

Share Button
A propos

Webmaster et rédacteur occasionnel du site. N'hésitez pas à me transmettre les modifications qui amélioreront votre utilisation du site.

Publié dans Informatique

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>