nothus

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…