Définition

• Un nombre premier est un entier naturel supérieur à 1 qui n’a que deux diviseurs distincts : 1 et lui-même.
• 0 et 1 ne sont donc pas des nombres premiers.
• Le premier nombre premier est donc 2. Oui, 2 est un nombre premier car il répond à la définition : DEUX diviseurs uniquement, 1 et lui-même.
• 2 est le seul nombre premier pair.

Algorithme naïf
Puisque les nombres pairs supérieurs à 2 sont des multiples de 2, ils ne sont donc pas des nombres premiers.


Un algorithme pour déterminer si un nombre est premier consiste à vérifier :

• s’il est un nombre impair
• s’il est divisible par aucun nombre premier inférieur

Une méthode efficace teste les diviseurs impairs jusqu’à ce nombre : si aucune division n’aboutit, le nombre est premier.

Une autre teste sa divisibilité par les nombres premiers inférieurs ou égaux à sa racine carrée : si aucune division n’aboutit, le nombre est premier.

Le crible d’Ératosthène est privilégié pour lister les premiers.

Pseudo code :

Fonction prem1(n) :
Si n = 0 ou n = 1 alors : retourner Faux
Pour i de 2 à n − 1 faire :
Si i divise n alors :
retourne False
Fin Pour
Retourer Vrai

Décomposition en Produit de Facteurs Premiers

Tout nombre entier supérieur ou égal à 2 peut être décomposé en une multiplication de nombres premiers. Décomposer des nombres en produit de facteurs premiers a plusieurs utilités, comme la simplification de fractions, la recherche du plus grand commun diviseur (PGCD) ou encore du plus petit commun multiple (PPCM).

Exemple :

La décomposition de 84 en facteurs premiers est :

84 = 2 × 2 × 3 × 7

Ce qui peut aussi s’écrire :

84 = 2² × 3 × 7
Simplification de Fractions

Décomposons 72 et 108 en facteurs premiers :
72 = 2 × 2 × 2 × 3 × 3
108 = 2 × 2 × 3 × 3 × 3
En annulant les facteurs communs, nous obtenons :

Trouver le PGCD (plus grand commun diviseur)

Pour trouver le PGCD de 72 et 108, prenons les facteurs premiers communs avec les plus petits exposants :

72 = 2³ × 3²
108 = 2² × 3³

Le PGCD est 2² x 3² = 36.
Trouver le PPCM (plus petit commun multiple)

Pour trouver le PPCM de 72 et 108, prenons les facteurs premiers avec les plus grands exposants :

72 = 2³ × 3²
108 = 2² × 3³

Le PPCM est 23 × 33 = 216.

Questions :

Implémenter ce pseudo code en python dans un notebook

Déterminer le nombres d’opérations T(100) réalisées pour n = 100. On considèrera comme opérations significatives les opérations arithmétiques et les comparaisons. Les comparaisons réalisées dans l’instruction Pour ... faire : ne seront pas comptées. Seules les instructions DANS la boucle seront considérées significatives.

Amélioration : nous allons modifier la borne supérieure dans la boucle, et diminuer le nombre d’opérations…

Soit n un entier supérieur ou égal à 2. Si n n’est pas premier, et si d est son plus petit diviseur supérieur ou égal à 2, on peut écrire :
n=d×quotient, avec d≤quotient

Imaginons par exemple que l’on recherche les diviseurs de 54 : Les diviseurs sont 2, 3, 6, 9, 18, 27.

Mais 18 et 27 sont egalement multiples de 2 et de 3. Donc, pour tester si un nombre est premier, il ne sera pas necessaire de tester toutes les valeurs de d. En pratique, il suffira de tester si n est divisible par des valeurs de d telles que :
d×d≤n

C’est à dire des entiers dont le carré est inférieur ou égal à n.

Questions :

Modifier le code dans une nouvelle fonction (que vous renommerez prem2) pour que celle-ci execute le moins d’opérations possibles. (soit le plus efficace).

Déterminer le nombre d’opérations T(100) réalisées pour n = 100.

Votre fonction, calcule t-elle bien ?

Programmer une fonction liste_prime qui utilise votre fonction prem2 pour établir la liste des nombres premiers de 0 à 100.
Faites une recherche documentaire pour trouver la liste des nombres premiers entre 0 et 100. Appelons cette liste wiki
Programmer une fonction compare qui détermine si tous les nombres de votre liste (donnés par prem2) font partie de celle wiki.

L’algorithme le plus efficace

L’algorithme le plus efficace est celui qui prend le moins de temps pour effectuer la même tâche.

On peut mesurer le temps d’exécution des programmes à l’aide du module time. Après avoir importé le module, il suffit de créer une variable t = time.time() que l’on mettra au debut de la fonction liste_prime.

Puis avant la sortie, d’afficher en console (print) le temps écoulé avec l’instruction : print(time.time()-t).

Tester les différentes fonctions prem1, prem2 avec les entiers premiers. Choisir une plus grande valeur pour N (10000 par exemple).

Créer vos modules de test

Vous allez maintenant realiser un test unitaire sur votre fonction prem2. Pour faire cela, vous allez réorganiser vos fonctions dans différents fichiers, et créer des modules.

Suivre l’énoncé du TP à la page /posts/python/Python_unittest_np/
Liens

Les nombres premiers, podcastsciences
Comment les nombres premiers protègent vos données : loic_demeulenaere

Un entier naturel est un nombre entier positif ou nul (
) utilisé pour compter des objets. Ces nombres forment un ensemble infini noté
. Ils ne possèdent pas de partie décimale (pas de virgule) et sont toujours supérieurs ou égaux à zéro

La Science au péril de sa vie