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.

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.

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.

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$

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.

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.

2.3. Trouver les cinquante premiers nombres premiers

La traduction en Python est la suivante (nombre_premier_cinquante_premiers_v1.py) :
Warning: file_get_contents(polytech/nombre_premier_cinquante_premiers_v1.py): Failed to open stream: No such file or directory in /home/jeanmichel.richer/public_html/ez_web.php on line 397

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) :
Warning: file_get_contents(polytech/nombre_premier_cinquante_premiers_v2.py): Failed to open stream: No such file or directory in /home/jeanmichel.richer/public_html/ez_web.php on line 397

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
Warning: file_get_contents(polytech/trouve_premiers_fonction.py): Failed to open stream: No such file or directory in /home/jeanmichel.richer/public_html/ez_web.php on line 397

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

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

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