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.


stacks
counter_1    accueil counter_2    cours counter_3   travaux pratiques

1.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, ...

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

On désire écrire une fonction en Python qui accepte un argument entier et qui permet de déterminer si un nombre est premier ou non. On renverra True si le nombre est premier, sinon on renverra False

On va par la suite écrire plusieurs versions.

1.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 distincts alors il est premier car ses seuls diviseurs sont 1 et $n$

Voici l'algorithme de la fonction à implanter :

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    ens/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$

Exercice 1.1

Ecrire le programme nombres_premiers_compte_diviseurs.py qui calcule les nombres premiers entre 1 et $N$ en utilisant la fonction est_premier(n). $N$ est un paramètre qui sera passé au programme. Regarder sous Google comment faire en utilisant le package sys.

En résultat on affichera, la liste des nombres premiers et la somme des nombres de la liste.

python3 python3 nombres_premiers_compte_diviseurs.py 100
 
[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]
1,060

Exercice 1.2

Mettre en commentaire l'affichage de la liste des nombres premiers.

Calculez le temps d'exécution pour la recherche des nombres premiers entre 1 et 20000 en utilisant la commande time du shell.

Voici le résultat sur AMD Ryzen 5 5600G :

\$ time python3 nombres_premiers_compte_diviseurs.py 20000
sum = 21,171,186

real	0m5,704s
user	0m5,694s
sys	0m0,008s

1.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.

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    ens/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

Exercice 1.3

Ecrire le programme nombres_premiers_efficace.py qui calcule les nombres premiers entre 1 et $N$ en utilisant la nouvelle fonction est_premier(n).

Tout comme dans le programme précédent, en résultat on affichera la somme des nombres de la liste.

Exercice 1.4

Calculez le temps d'exécution pour la recherche des nombres premiers entre 1 et 20000 en utilisant la commande time du shell.

Que remarquez vous ?

1.2.3. 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    ens/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 1.5

Ecrire le programme nombres_premiers_crible.py qui calcule les nombres premiers entre 1 et $N$ en utilisant la méthode du crible.

Tout comme dans le programme précédent, en résultat on affichera la somme des nombres de la liste.

Exercice 1.6

Calculez le temps d'exécution pour la recherche des nombres premiers entre 1 et 20000 en utilisant la commande time du shell.

1.3. Conjecture de Collatz

S'il vous reste du temps...

On appelle suite de Collatz (Lothar Collatz), une suite de nombres générée par la fonction de Collatz appliquée récursivement à partir d'un entier naturel $n$.

La fonction de Collatz est une fonction récursive applicable à tout entier positif $n$, définie par :

  • si $n$ est pair, alors $n=n/2$
  • si $n$ est impair, alors $n = 3n+1$

La conjecture de Collatz, ou conjecture de Syracuse, énonce qu'une suite de Collatz se termine par $1$.

Exercice 1.7

Ecrire le programme collatz.py qui permet de le vérifier pour tout $n$. On s'arrêtera dès que $n = 1$.

On testera pour $n = 27$.

[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Cette suite comporte 112 termes.

Attention, il faut utiliser la division entière : //.