Discussion :

[Krayon70]

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 :

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
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 !")

[tyrtamos]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Sve@r]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Sve@r]

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 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é)

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

[Krayon70]

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

Yvan

[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.

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 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
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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[wiztricks]

Qui l'aurait cru ? Remarque avec le recul (c'est toujours plus facile d'expliquer les choses avec le recul !!! ) 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...

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

- W

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

[Sve@r]

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

[Krayon70]

Eh bien messieurs, on peut dire que vous allez au bout des choses... Très intéressant et instructif !

[wiztricks]

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

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

- W

[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 !