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.

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
  1. fonction est_premier(n est un entier) : booléen
  2.  
  3.   // initialement on n'a aucun diviseur
  4.   nbr_diviseurs est un entier = 0
  5.  
  6.  
  7.   // on recherche les diviseurs potentiels
  8.   pour i de 1 à n faire
  9.     si i est_un_diviseur_de n alors
  10.       nbr_diviseurs = nbr_diviseurs + 1
  11.     fin si
  12.   fin pour
  13.  
  14.   // en fonction du nombre de diviseurs on indique
  15.   // si le nombre est premier ou non
  16.   si nbr_diviseurs == 2 alors
  17.     retourner vrai
  18.   sinon
  19.     retourner faux
  20.   fin si
  21.  
  22. fin fonction 
  23.  

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

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.

  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 :

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$
  1. fonction est_premier(n est un entier) : booléen
  2.  
  3.   i est un entier
  4.  
  5.   si n <= 1 alors
  6.     retourner faux
  7.   sinon si 2 <= n et n <= 3 alors
  8.     retourner vrai
  9.   sinon si n est_disible_par 2 alors
  10.     retourner faux
  11.   sinon
  12.     // rechercher des diviseurs
  13.     pour i de 3 à sqrt(n)+1 par pas de 2 faire
  14.       si n est_divisible_par i alors
  15.         retourne faux
  16.       fin si
  17.     fin pour
  18.   fin si
  19.  
  20.   // aucun diviseur trouvé, le nombre est premier
  21.   retourner vrai
  22.  
  23. fin fonction 
  24.  

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 :

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

  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
  1. // liste des nombres premiers
  2. liste est une liste entiers = vide
  3.  
  4. // nombre courant
  5. n est un entier = 1
  6.  
  7. tant que taille liste != 50 faire
  8.  
  9.   si est_premier(n) alors
  10.     ajouter n à liste
  11.   fin si
  12.   n = n + 1
  13.  
  14. fin tant que
  15.  

La traduction en Python est la suivante (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) :

  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

  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 :

Crible

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

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.