Script nombre premier et problème de division

Version imprimable

Bonjour à toutes et tous,

Je débute en Python et je me suis lancé dans un script (cf. ci-dessous) qui teste si un nombre est premier.
Cela fonctionne parfaitement en utilisant des nombres plus petits que 10^12 (p.ex. 1000000008673).
Malheureusement, en utilisant des nombres plus grands et impairs, l'interpréteur (repl.it ou IDLE sur Mac) me dit que le nombre se divise par 2 :( (p.ex. 100000000867300001)
Il semblerait que cela provienne d'un "problème" de division...
Quelqu'un peut-il m'aider.
Merci d'avance.

Yvan

Voici mon script :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from math import *
while True: # s'exécute tant le nombre saisi n'est pas un entier supérieur à 1
    try:
        nombre = int(input("Entrer un entier positif supérieur à 1 : "))
        if nombre > 1:
            break
    except ValueError:
        continue
if nombre == 2:
  print("_____________________________________________________")
  print(nombre, "est un nombre premier !")
else:
  if nombre/2 == nombre//2:
    print("_____________________________________________________")
    print(nombre, "n'est pas premier car il se divise par 2")
  else:
    compteur = 0
    limite = int(sqrt(nombre)) # tester les diviseurs jusqu'à la racine carré du nombre saisi
    for x in range (3, limite + 1):
      if nombre/x == nombre//x:
        compteur = compteur + 1 
        break       
    if compteur > 0:
      print("_____________________________________________________")
      print(nombre, "n'est pas premier car il se divise par", x)
      print(nombre, ":", x, "=", nombre//x)
      #print(x)
    else:
      print("_____________________________________________________")
      print(nombre, "est un nombre premier !")

Bonjour

C'est le test "if nombre/x == nombre//x:" qui n'est pas bon puisque nombre/x donne un nombre flottant qui ne sera pas forcément exact à cause de la représentation des nombres flottants en mémoire.

Par exemple:
Code:

1 2 print(10**50/2==10**50//2) False
Comme on utilise ici des nombres entiers, il faut utiliser l'opérateur modulo "%", et ce test devrait être "if nombre%x==0:", c'est à dire "reste de la division entière de nombre par x == 0".

Par ailleurs, dès lors qu'on a traité les nombres pairs (dont seul 2 est premier), il ne faut plus essayer que les nombres impairs dans la boucle for, donc avec un pas de 2 à partir de 3.

L'algorithme serait d'ailleurs plus facile à mettre au point s'il était dans une fonction "estpremier(n)" renvoyant True ou False selon le cas.
Un exemple de pseudo-code de cette fonction:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 fonction estpremier(n) si n<2: renvoyer faux car aucun nb premier en dessous de 2 si n est pair: renvoyer vrai seulement si n est égal à 2, faux sinon boucle: on essai de k=3 jusqu'à racine(n)+1 avec un pas de 2: si n est divisible par k: renvoyer faux renvoyer vrai puisque aucun diviseur n'a été trouvé: n est premier

Bonjour
Une autre possibilité est de boucler jusqu'à ce que n/k devienne plus petit que k. Si en effet n/k donne x plus petit, alors on aurait trouvé n/x donne k lors des tests. Donc si n/k devient plus petit que k, le nombre est premier.
C'est équivalent à aller jusqu'à racine(n) comme le dit Tyrtamos. Toutefois Python t'offre la fonction divmod() qui donne en une opération le résultat de la division et son reste.

Donc l'algo deviendrait
Code:

1 2 3 4 5 6 7 8 9 10 11 fonction estpremier(n) si n<=2: renvoyer vrai si n = 2 sinon faux si n est pair: renvoyer faux si n in (3, 5): renvoyer vrai # On peut rajouter 7, 11, etc si on veut donner un départ connu boucle: on part de k=3 dans une boucle infinie (q, r)=divmod(n, k) si r == 0: renvoyer faux si q < k: renvoyer vrai k+=2

18/09/2020, 10h47
tyrtamos
Bonjour Sve@r,

Bravo pour avoir évité le calcul de la racine carrée: c'est toujours ça de pris pour accélérer le calcul.

J'ai vérifié, et ton algorithme donne le bon résultat, avec une légère correction. En effet, si n=3, on a divmod(3, 3) => q=1 et r=0. Cela échoue avec la condition if r==0. Or, si un nombre premier est divisible par lui-même, il reste premier. Il suffit donc de compléter la condition:
Code:

1 2 if r==0 and q!=1: return False
Et là, on retrouve tout.

J'ai vérifié aussi que le nombre de tour de boucles est la même (à 1 près) avec la solution utilisant la racine.

Merci!

Ajout supplémentaire. Pour accélérer les calculs, on pourrait théoriquement se contenter d'essayer de diviser avec la liste des nombres premiers inférieurs déjà connus. C'est ce qu'il faudrait faire si on voulait établir une liste de nombres premiers croissants en utilisant les résultats précédents.

Citation:

Envoyé par tyrtamos

J'ai vérifié, et ton algorithme donne le bon résultat, avec une légère correction. En effet, si n=3, on a divmod(3, 3) => q=1 et r=0. Cela échoue avec la condition if r==0. Or, si un nombre premier est divisible par lui-même, il reste premier.

Héhé, t'as pas remarqué que j'avais testé certains nombres dès le départ dont ce fameux 3 :D Effectivement lui et son prédecesseur sont les seuls nombres premiers qui font foirer l'algo.
Ceci dit, j'aime pas trop mon départ (j'ai tapé ça vite fait ce matin). Je crois que l'algo serait mieux ainsi
Code:

1 2 3 4 5 6 fonction estpremier(n) si n in (2, 3, 5): renvoyer vrai # On peut rajouter 7, 11, etc pour éviter les calculs de nombres déjà connus mais il faut laisser au-moins 2 et 3 si n < 2 ou n pair renvoyer faux # Elimine 1, 0, les négatifs et tous les pairs (2 a déjà été sauvé) boucle: on part de k=3 dans une boucle infinie .... (le reste inchagé)
Citation:

Envoyé par tyrtamos

Ajout supplémentaire. Pour accélérer les calculs, on pourrait théoriquement se contenter d'essayer de diviser avec la liste des nombres premiers inférieurs déjà connus. C'est ce qu'il faudrait faire si on voulait établir une liste de nombres premiers croissants en utilisant les résultats précédents.

Oui, effectivement ça accélère la recherche... mais ça impose alors de tout calculer. Plus possible alors de tester 1547 sans avoir testé avant les 1546 autres (enfin seulement les impairs quoi). Avec les algorithmes de recherche mathématiques on est toujours à devoir choisir entre tel avantage (qui entraine tel inconvénient) ou tel autre (qui entraine alors tel autre inconvénient en retour).

18/09/2020, 20h56
Krayon70

Merci !

Un grand merci pour vos remarques et conseils précieux... TOP !
Meilleures salutations.

Yvan

Citation:

Envoyé par tyrtamos

Bravo pour avoir évité le calcul de la racine carrée: c'est toujours ça de pris pour accélérer le calcul.

Hé bien il se trouve qu'en fait, non. Pourtant moi aussi j'y croyais...

Je viens de faire un petit benchmark pour comparer ton algo et le mien. J'ai choisi le nombre 1000 000 000 193 qui se trouve être le premier nombre premier qui dépasse 1000 milliards
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #!/usr/bin/python3 # -*- coding: utf-8 -*- from time import time # Lance une fonction n fois et renvoie le temps global def timereps(reps, func, *args): start = time() for i in range(reps): r=func(*args) end = time() return (r, end - start) # def timereps # Calcul par la racine selon l'algo donné par Tyrtamos def racine(n): if n < 2: return False if (n%2) == 0: return n == 2 for k in range(3, int(n**0.5) + 1, 2): if (n%k) == 0: return False return True # racine # Calcul par dépassement du diviseur def depassement(n): if n in (2, 3, 5): return True if n < 2 or (n%2) == 0: return False k=3 while True: #(q, r)=divmod(n, k) if (n%k) == 0: return False if (n//k) < k: return True k+=2 # while # depassement if __name__ == "__main__": test=1000000000193 for (l, f) in ( ("racine", racine), ("depassement", depassement), ): r=timereps(1000, f, test) print(l, test, r) # for # if
Et voici le résultat
Code:

1 2 3 moi@moi-VirtualBox:~$ ./primes.py racine 1000000000193 (True, 38.41981625556946) depassement 1000000000193 (True, 54.95302891731262)
j'ai ensuite pensé que divmod() prenait du temps (appel de fonction) donc je l'ai remplacé par les vraies opérations de division et du modulo mais le résultat a à peine été meilleur
Code:

1 2 3 moi@moi-VirtualBox:~$ ./primes.py racine 1000000000193 (True, 38.88724207878113) depassement 1000000000193 (True, 51.74536347389221)
Qui l'aurait cru ? Remarque avec le recul (c'est toujours plus facile d'expliquer les choses avec le recul !!! 8-)) ton algorithme par la racine carrée ne fait qu'une opération par boucle, tandis que le mien par dépassement en fait deux... :chin:

19/09/2020, 12h41
wiztricks

Citation:

Envoyé par Sve@r

Qui l'aurait cru ? Remarque avec le recul (c'est toujours plus facile d'expliquer les choses avec le recul !!! 8-)) ton algorithme par la racine carrée ne fait qu'une opération par boucle, tandis que le mien par dépassement en fait deux... :chin:

Côté majoration du nombre d'itération, n / 2 est plus grand que racine de n.

- W
19/09/2020, 12h53
tyrtamos

Bonjour Sve@r

J'ai eu la même recherche ce matin en comparant les temps de calcul, et je trouve aussi que ton calcul est un peu plus long. En fait, le calcul de la racine n'est faite qu'une seule fois puisqu'elle ne dépend que de n (à faire avant le while!), alors que la division entière doit être renouvelée à chaque tour de boucle.

Il est possible aussi que le calcul de la racine soit rapide grâce à l'unité d'arithmétique rapide des CPU modernes (j'ai connu une époque lointaine où il fallait acheter une puce spéciale, AMD9511 pour moi, pour avoir les fonctions mathématiques codées en hard, mais j'avais dû établir la liaison en assembleur...). J'ai d'ailleurs essayé aussi ce matin le calcul en Python de la racine entière selon l'algorithme d'Euclide, et je ne trouvais alors plus de différence sensible avec ta solution, mais cette fonction aurait mérité d'être convertie en C pour être homogène.

Il faut reconnaître aussi que le test de primalité par division est assez rapide en Python jusqu'à une vingtaine de chiffres. Au delà, il faut utiliser d'autres algorithmes comme celui de Miller-Rabin: on peut alors obtenir un résultat sur des nombres de plusieurs centaines de chiffres en quelques minutes, même si ce résultat est probabiliste. Mais on est très loin de pouvoir casser le cryptage RSA avec ça (heureusement). :D
19/09/2020, 13h16
Sve@r

Citation:

Envoyé par wiztricks

Côté majoration du nombre d'itération, n / 2 est plus grand que racine de n.

Mmmoui mais je ne fais pas n/2 itérations. En m'arrêtant quand n/k devient plus petit que k, cela équivaut en nombre d'itérations à racine(n). Dans les deux algos le nombre d'itérations est le même (à 1 près).
19/09/2020, 15h52
Krayon70

...

Eh bien messieurs, on peut dire que vous allez au bout des choses... Très intéressant et instructif ! :D
19/09/2020, 16h39
wiztricks

Citation:

Envoyé par Sve@r

Mmmoui mais je ne fais pas n/2 itérations. En m'arrêtant quand n/k devient plus petit que k, cela équivaut en nombre d'itérations à racine(n). Dans les deux algos le nombre d'itérations est le même (à 1 près).

:oops: j'ai lu votre code en diagonale un peu trop pentue.

- W
21/09/2020, 18h01
lg_53

Les tests conditionnels semblent effectivement couter cher.
Si on fait le benchmark sur un nombre premier plus petit, il y a fort à parier que les différences soit plus petites, voire carrément inversée !