Algorithmes des nombres premiers

Definition

Nombre premier: un nombre premier est un nombre qui accepte DEUX diviseurs : uniquement lui-même et 1.

Algorithme naïf

Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier.

Le test le plus simple est le suivant : pour tester N , on vérifie s’il est divisible par l’un des entiers compris au sens large entre 2 et N − 1. Si la réponse est positive (True), alors N est premier, sinon il est composé (multiple).

Les nombres 0 et 1 ne sont pas considérés comme 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

Questions:

1. Implémenter ce pseudo code en python dans un notebook

2. 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\times quotient,~avec~d \leq 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 \times d \leq n$$ C’est à dire des entiers dont le carré est inférieur ou égal à n.

Questions:

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

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

Votre fonction, calcule t-elle bien?

1. Programmer une fonction liste_prime qui utilise votre fonction prem2 pour établir la liste des nombres premiers de 0 à 100.
2. Faites une recherche documentaire pour trouver la liste des nombres premiers entre 0 et 100. Appelons cette liste wiki
3. 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