Site de Jean-Michel RICHER

Maître de Conférences en Informatique à l'Université d'Angers

Ce site est en cours de reconstruction certains liens peuvent ne pas fonctionner ou certaines images peuvent ne pas s'afficher.


Cette page fait partie du cours de polytech PeiP1 et 2 Bio

2. Mise en pratique : nombres premiers

2.1. Introduction

Dans ce TP, on s'intéresse aux nombres premiers, à leur identification et leur recherche.

On rappelle la définition d'un nombre premier : il s'agit d'un entier naturel qui possède deux diviseurs distincts : 1 et lui-même.

En conséquence le nombre 1 n'est pas premier car il ne possède qu'un seul diviseur.

La liste des premiers nombres premiers est : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, ...

2.2. Déterminer si un nombre est premier ou non

Ecrire une fonction qui permet de déterminer si un nombre est premier ou non.

2.2.1. Première version naïve et lente

Dans un premier temps, on détermine si un nombre est premier ou non en comptant son nombre de diviseurs.

  • si un nombre $n$ ne possède que deux diviseurs alors il est premier car ses seuls diviseurs sont 1 et $n$

Cliquez sur la zone orangée pour voir apparaître les informations complémentaires liées à la fonction ci-dessous.

fonction est_premier(n)
Entrée n (entier) : nombre pour lequel on doit déterminer s'il est premier ou non
Sortie booléen, vrai si n est premier, faux sinon
Variables
locales		 nbr_diviseurs (entier) : compte le nombre de diviseurs de n
Description On calcule le nombre de diviseurs de n,
s'il en existe deux alors le nombre est premier
Afficher le code    polytech/est_premier_compte_diviseurs.algo
  1. // initialement on n'a aucun diviseur
  2. nbr_diviseurs est un entier = 0
  3.  
  4.  
  5. // on recherche les diviseurs potentiels
  6. pour i de 1 à n faire
  7.   si i est_un_diviseur_de n alors
  8.     nbr_diviseurs = nbr_diviseurs + 1
  9.   fin si
  10. fin pour
  11.  
  12. // en fonction du nombre de diviseurs on indique
  13. // si le nombre est premier ou non
  14. si nbr_diviseurs == 2 alors
  15.   retourne vrai
  16. sinon
  17.   retourne faux
  18. fin si
  19.  

La seule difficulté rencontrée consiste à déterminer si $i$ est un diviseur de $n$ :

  • si $i$ est un diviseur de $n$ cela signifie que $n = i × p$.
  • dans le cas contraire, cela implique que $n = i × p + r$ ; en d'autres termes, si on divise $n$ par $i$, on aura un reste $0 < r < i$.

Pour trouver le reste de la division on utilise l'opération modulo : $n\ %\ i$

L'implantation en Python est assez simple (est_premier_compte_diviseurs.py). Cliquez sur la première ligne du code pour faire apparaître l'ensemble des instructions.

Afficher le code    polytech/est_premier_compte_diviseurs.py
  1. def est_premier(n):
  2.   """
  3.     est_premier(n)
  4.    
  5.     Détermine si un nombre est premier ou non.
  6.     Cette version compte le nombre de diviseurs.
  7.    
  8.     Parameters
  9.     ----------
  10.     n : int
  11.       nombre pour lequel on veut déterminer s'il est premier ou non
  12.    
  13.     Returns:
  14.       True si n est premier, False sinon
  15.   """
  16.   nbr_diviseurs = 0
  17.  
  18.   # pour chaque nombre entre 1 et n
  19.   for i in range(1, n+1):
  20.     # si i est un diviseur de n alors
  21.     if n % i == 0:
  22.       # augmenter le compteur
  23.       nbr_diviseurs = nbr_diviseurs + 1
  24.  
  25.   if nbr_diviseurs == 2:
  26.     return True
  27.   else:
  28.     return False
  29.  
  30.  

2.2.2. Deuxième version améliorée et efficace

La version précédente n'est pas efficace pour plusieurs raisons :

  • on évalue tous les diviseurs ce qui implique beaucoup de calculs si $n$ est grand
  • il suffit de trouver un diviseur qui soit différent de 1 et de $n$ pour déterminer que $n$ n'est pas premier
  • il n'est pas nécessaire de tester tous les diviseurs pairs à partir du moment ou $n$ est divisible par 2
  • il faut limiter la recherche des diviseurs à $√(n)+1$

Prenons un exemple ($n = 37$) pour comprendre pourquoi il ne faut pas aller au-delà de $√(37)+1$

 diviseurs   quotient   reste 
 1   37   0 
 2   18   1 
 3   12   1 
 4   9   1 
 5   7   2 
 6   6   1 
 7   5   2 
 8   4   5 
 9   4   1 
 10   3   7 
 etc   etc   etc 
Recherche des diviseurs de 37

Au-delà de 7 les quotients seront nomarlement inférieurs à 7, or on a déjà testé les diviseurs de 1 à 7.

Voici l'algorithme de la fonction est_premier basée sur le calcul du nombre de divisieurs. Cliquez sur la zone orangée pour voir apparaître les informations complémentaires.

Fonction est_premier(n)
Entrée n (entier) : nombre pour lequel on doit déterminer s'il est premier ou non
Sortie booléen, vrai si n est premier, faux sinon
Description On cherche les diviseurs impairs de 3 à $√(n)+1$
Afficher le code    polytech/est_premier_amelioree.algo
  1. i est un entier
  2.  
  3. si n <= 1 alors
  4.   retourne faux
  5. sinon si 2 <= n et n <= 3 alors
  6.   retourne vrai
  7. sinon si n est_disible_par 2 alors
  8.   retourne faux
  9. sinon
  10.   // rechercher des diviseurs
  11.   pour i de 3 à sqrt(n)+1 par pas de 2 faire
  12.     si n est_divisible_par i alors
  13.       retourne faux
  14.     fin si
  15.   fin pour
  16. fin si
  17.  
  18. // aucun diviseur trouvé, le nombre est premier
  19. retourne vrai
  20.  

L'implantation en Python pose un seul problème lié à la racine carrée car elle fait partie des calculs sur les nombres réels :

  • il est nécessaire de faire appel à la fonction sqrt (square root) de la librairie mathématique (math)
  • il faut convertir le résultat en entier

Voici le script correspondant (est_premier_amelioree.py). Cliquez sur la première ligne du code pour faire apparaître l'ensemble des instructions.

Afficher le code    polytech/est_premier_amelioree.py
  1. import math
  2.  
  3. def est_premier(n):
  4.   if n <= 1:
  5.     return False
  6.  
  7.   if n <= 3:
  8.     return True
  9.    
  10.   if n % 2 == 0:
  11.     return False
  12.    
  13.   for i in range(3, int(math.sqrt(n)+1), 2):
  14.     if n % i == 0:
  15.       return False
  16.  
  17.   return True
  18.  
  19.  

2.3. Trouver les cinquante premiers nombres premiers

Programme
Description Calcule les 50 premiers nombres premiers en les stockant dans une liste
Afficher le code    polytech/nombre_premier_cinquante_premiers.algo
  1. // liste des nombres premiers
  2. liste est une liste entiers = vide
  3.  
  4. // nombre courant
  5. n est un entier = 1
  6.  
  7. tantque taille liste != 50 faire
  8.   si est_premier(n) alors
  9.     ajoute n à liste
  10.   fin si
  11.   n = n + 1
  12. fin tantque
  13.  

La traduction en Python est la suivante (nombre_premier_cinquante_premiers_v1.py) :

Afficher le code    polytech/nombre_premier_cinquante_premiers_v1.py
  1. import est_premier_amelioree as premier
  2. # ou import est_premier_compte_diviseurs as premier
  3.  
  4. # liste vide
  5. liste = []
  6. # on commence la recherche avec n = 1
  7. n = 1
  8.  
  9. # tant qu'on n'a pas 50 nombres premiers on continue la recherche
  10. while len(liste) != 50:
  11.   if premier.est_premier(n):
  12.     liste.append(n)
  13.   n = n + 1
  14.  
  15. print(liste)
  16.  

On peut également utiliser une fonctionnalité de Python qui consiste à générer une liste en indiquant comment générer chaque élément : (nombre_premier_cinquante_premiers_v2.py) :

Afficher le code    polytech/nombre_premier_cinquante_premiers_v2.py
  1. import est_premier_amelioree as premier
  2. # ou import est_premier_compte_diviseurs as premier
  3.  
  4. """ deuxième méthode
  5. autre manière d'obtenir le même résulat en
  6. remplissant une liste mais on ne peut contrôler
  7. la longueur de la liste
  8. """
  9. liste = [ x for x in range(1,300) if premier.est_premier(x) ]
  10.  
  11. # sélection des cinquante premiers de l'indice 0 à l'indice 49
  12. liste = liste[0:50]
  13. print(liste)
  14.  

2.4. Trouver les nombres premiers dans un intervalle

Une fois que l'on est en mesure de déterminer si un nombre est premier ou non, on peut commencer à rechercher les nombres premiers.

2.4.1. Utiliser la fonction est_premier

Voici un exemple de programme qui permet de rechercher les nombres premiers dans un intervalle donné. On passe en paramètre du programme

Afficher le code    polytech/trouve_premiers_fonction.py
  1. import math
  2. import sys, getopt
  3. """
  4.   programme qui trouve les nombres premiers dans un intervalle
  5. """
  6.  
  7.  
  8. def est_premier(n):
  9.   """
  10.     est_premier(n)
  11.    
  12.     Détermine si un nombre est premier ou non.
  13.     Cette version compte le nombre de diviseurs.
  14.    
  15.     Parameters
  16.     ----------
  17.     n : int
  18.       nombre pour lequel on veut déterminer s'il est premier ou non
  19.    
  20.     Returns:
  21.       True si n est premier, False sinon
  22.   """
  23.   if n <= 1:
  24.     return False
  25.  
  26.   if n <= 3:
  27.     return True
  28.    
  29.   if n % 2 == 0:
  30.     return False
  31.    
  32.   for i in range(3, int(math.sqrt(n)+1), 2):
  33.     if n % i == 0:
  34.       return False
  35.  
  36.   return True
  37.  
  38.  
  39. def trouve_nombres_premiers(maximum):
  40.   """
  41.     trouve_premiers(n)
  42.    
  43.     Trouve tous les nombres premiers dans un
  44.     intervalle donné
  45.    
  46.     Parameters
  47.     ----------
  48.     maximum : int
  49.       borne supérieure de l'intervalle de recherche
  50.    
  51.     Returns:
  52.       liste des nombres premiers
  53.   """
  54.   # liste des nombres premiers
  55.   nombres_premiers = []
  56.  
  57.   # recherche des nombres premiers entre 1 et 100
  58.   for n in range(1,maximum+1):
  59.     if est_premier(n):
  60.       nombres_premiers.append(n)
  61.  
  62.   return nombres_premiers
  63.        
  64.  
  65. def main():
  66.   """
  67.     fonction principale
  68.    
  69.     on peut passer en argument du programme la borne supérieure
  70.     de l'intervalle de recherche en utilisant l'argument '-m val'
  71.     ou '--maximum=val'
  72.   """
  73.   maximum = 100000
  74.   try:
  75.     opts, args = getopt.getopt(sys.argv[1:], "hm:", ["help", "maximum="])
  76.   except getopt.GetoptError as err:
  77.     # print help information and exit:
  78.     print(err) # will print something like "option -a not recognized"
  79.     usage()
  80.     sys.exit(2)
  81.   for o, a in opts:
  82.     if o == "-m":
  83.       maximum = int(a)
  84.     elif o in ("-h", "--help"):
  85.       usage()
  86.     else:
  87.       assert False, "unhandled option"
  88.  
  89.   l = trouve_nombres_premiers(maximum)
  90.   print( l )
  91.   print( "dans l'intervalle [1..{}]".format(maximum) )
  92.   print( "il y a ", len(l), " nombres premiers")
  93.   print( "leur somme est égale à ", sum(l) )
  94.  
  95.  
  96. if __name__ == "__main__":
  97.     main()
  98.      
  99.  

Voici quelques résultats qui permettent de comparer la méthode naïve avec la méthode améliorée :

 Méthode   temps (s)   somme 
 naïve   4m13s   454396537 
 améliorée   0,1   454396537 
Recherche des nombres premiers entre 1 et 10000 sur Intel i7-4790 CPU @ 3.60GHz

2.4.2. Crible d'Erathostène

Une autre solution, plutôt que de déterminer si un nombre $n$ est premier, consiste à utiliser un tableau de booléens tableau_nombres_premiers où chaque tableau_nombres_premiers[i] est vrai si $i$ est un nombre premier.

Pour remplir le tableau, on procède ainsi :

  • on indique qu'initialement tous les nombres sont premiers excepté 0 et 1
  • on commence avec l'indice $i=2$ qui sera incrémenté
  • pour tout tableau_nombres_premiers[i] affecté à vrai, on affecte tous ses multiples à faux

Crible

fonction
Description remplir un tableau et éliminer les multiples
Afficher le code    polytech/nombres_premiers_crible.algo
  1. // créer et remplir le tableau
  2. variable t est un tableau de [1 à maximum] booléens
  3.  
  4. pour i de 2 à maximum faire
  5.   t[i] = vrai
  6. fin pour
  7. t[0] = faux
  8. t[1] = faux
  9.  
  10. // éliminer les multiples
  11. pour i de 2 à maximum faire
  12.   si t[i] == vrai alors
  13.     pour j de 2*i à maximum par pas de i faire
  14.       t[j] = faux
  15.     fin pour
  16.   fin si
  17. fin pour
  18.  
  19. // créer et retourner la liste des nombres premiers
  20. variable l est une liste entiers = vide
  21.  
  22. pour i de 1 à maximum faire
  23.   si t[i] == vrai alors
  24.     ajouter i à l
  25.   fin si
  26. fin pour
  27. retourne l
  28.  

Exercice 2.1

Ecrire un programme Python très simple qui implante l'algorithme du crible.

On utilisera une liste de nombres entiers.

Voici un exemple qui utilise la librairie numpy (trouve_premiers_crible.py) mais on peut écrire quelque chose de beaucoup plus simple.