Voir le flux RSS

nothus

[Python3] Nombres premiers : trouver les énièmes premiers

Noter ce billet
par , 18/07/2017 à 15h50 (646 Affichages)
Rappel : un nombre premier est divisible pour un résultat entier naturel, seulement par un et par lui-même. Un résultat qui est un nombre décimal, exclut de fait le nombre voulu de l’ensemble des nombres premiers.

Exemple de nombres premiers : 2 et 3. Alors 5 est-il un nombre premier ?
… Soit : 5 / 2 = 2,5 => décimal ; 2 n’est pas un multiple de 5
… Soit : 5 / 3 = 1,666...7 => décimal ; 3 n’est pas un multiple de 5
… N’ayant pas d’autre nombre premiers entre 1 et 5…
… Alors 5 est un nombre premier !

Par contre 6 a deux multiples (2 et 3) ; 7 est premier ; 8 a un multiple (2, avec lui-même) ; 9 a un multiple (3, avec lui-même) ; etc.

L’intérêt de prendre non pas le modulo (le reste de la division) mais le résultat lui-même, permet de gagner en rapidité : en effet, un modulo différent de 0 n’est pas la preuve d’un nombre premier (8 / 2 = 4 ; hors 4 est un multiple de 2). De la même façon, il n’est pas nécessaire de tester systématiquement tous les nombres : seuls ceux déjà premiers sont intéressants lorsque l’on débute l’exercice. Par exemple : si l’on veut débuter le test à partir de l’entier 15, on part du préalable que les nombres premiers inférieurs à 15 sont connus (ici : 2 ; 3 ; 5 ; 7 ; 11 ; 13).

En Python, le plus simple est de tester systématiquement toutes les valeurs dans l’ensemble voulu. Par exemple si l’on commence à 4 :
… Soit nombres_premiers = [2, 3]
… Soit le parcours range(4, 4*2)
… On stock le résultat de l’opération de division pour chaque entier :
multiples[4] = { 2 : True, 3 : False }
… avec str(i/premier).endswith(".0") pour vérifier si le résultat de la division est bien en réalité un entier ! Car une division retourne toujours par défaut de type float - fût-ce avec une valeur qui est un entier naturel.

Il reste donc à trier nos résultats pour ne garder que les nombres premiers… L’exemple ci-dessous nous donne la liste des (environs) 50 nombres premiers – en effet on ne sait pas par avance combien chaque passage en trouve…

Code python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
premiers = [2, 3]
 
while len(premiers)<50: 
 
    multiples = {}
    max_premiers = max(premiers) 
    for i in range(max_premiers+1,max_premiers*2):
        multiples[i] = True 
        for premier in premiers:
            multiples[i] = multiples[i] and (
                False if str(i/premier).endswith(".0") else True
            ) 
 
    for i in multiples: 
        if multiples[i]:
            premiers.append(i) 
 
print( 
    premiers 
)

Retour (correct!) de la console :

Code python : Sélectionner tout - Visualiser dans une fenêtre à part
[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, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317]

Reste un problème : il y a beaucoup de récursions inutiles ; car dès qu’un multiple est trouvé, il est inutile d’en chercher d’autres. OUI MAIS : Python n’accepte pas de break pour plusieurs boucles… Astuce : la gestion des exceptions !

Code python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class PasPremier(Exception):
    pass 
 
premiers = [2, 3]
 
while len(premiers)<50: 
 
    multiples = []
    max_premiers = max(premiers) 
    for i in range(max_premiers+1,max_premiers*2):
        try:
            for premier in premiers:
                if (i/premier).is_integer(): 
                    raise PasPremier()
            multiples.append(i) 
        except PasPremier:
            pass 
 
    premiers = premiers+multiples 
 
print( 
    premiers 
)

Si l’on ajoute le décompte du temps, le gain de productivité est considérable et le code est en outre plus lisible :

  • Nbre de nombres premiers à trouver… float/str vs try / catch (en s)
  • Au moins 50 : 0,01288821434953094 / 0,0018349865856706153
  • Au moins 500 : 0,5129900689371096 / 0,0640265957566256
  • Au moins 1.000 : 1,6564472029126243 / 0,13277764036765174
  • Au moins 5.000 : (arrêt manuel après plus de 15 secondes) / 4,668996650507877
  • Au moins 10.000 : (arrêt manuel après plus de 15 secondes) / 16,362508016036244
  • Au moins 50.000 : (arrêt manuel après plus de 15 secondes) / 205,84759987283414


Le gain est important pour finalement peu de changements : la logique générale (mon résultat est-il un entier naturel ?) reste la même.

Si l’intérêt n’est pas flagrant pour un usage courant (les nombres premiers, une fois calculés une première fois, ont vocation à rester enregistrés), reste la beauté du code et aussi prouver – si cela devait être encore le cas – de la nécessité d’optimiser sa programmation…

Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog Viadeo Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog Twitter Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog Google Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog Facebook Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog Digg Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog Delicious Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog MySpace Envoyer le billet « [Python3] Nombres premiers : trouver les énièmes premiers » dans le blog Yahoo

Commentaires

  1. Avatar de Nothus
    • |
    • permalink
    Citation Envoyé par danielhagnoul
    J'ai vu Tu as bien fait, c'est important pour souligner / comparer les qualités et défauts de chaque langage et voir si des pistes d'amélioration sont possibles. Juste une question : pour imbriquer tes boucles de récursion ? Une seule avec la gestion des erreurs n'est-elle pas plus pertinente / efficace ?

    Pour être honnête, j'ai procéder à tâtons pour arriver à cet article et trouver "ma" solution. J'imagine qu'il doit en exister des plus performantes encore... ?

    Enfin je me suis servi de la piste sur les nombres premiers pour un nouvel article récent sur un moteur IFTTT. L'exportation vers JS et notamment NodeJS peut être utile pour une version déchargée vers le client ou encore pour proposer des micro-services à un serveur.