Python: Calculer les nombres premiers
class LowerThanTwo(Exception):
pass
def isPrime(num):
try:
num = int(num)
if num < 2: raise LowerThanTwo()
except ValueError:
return False, "Saisir un nombre valide !!!"
except LowerThanTwo:
return False, "Saisir un nombre supérieur égal à 2 !!!"
else:
if num > 2 and num % 2 == 0:
return False, "{:>5d} n'est pas un nombre premier!".format(num)
for x in range(2, num // 2):
if num % x == 0:
return False, "{:>5d} n'est pas un nombre premier!".format(num)
return True, "{:>5d} est un nombre premier!".format(num)Exécution de la fonction:
for x in range(100):
a, b = isPrime(x)
if a: print(b)
2 est un nombre premier!
3 est un nombre premier!
5 est un nombre premier!
7 est un nombre premier!
11 est un nombre premier!
13 est un nombre premier!
17 est un nombre premier!
19 est un nombre premier!
23 est un nombre premier!
29 est un nombre premier!
31 est un nombre premier!
37 est un nombre premier!
41 est un nombre premier!
43 est un nombre premier!
47 est un nombre premier!
53 est un nombre premier!
59 est un nombre premier!
61 est un nombre premier!
67 est un nombre premier!
71 est un nombre premier!
73 est un nombre premier!
79 est un nombre premier!
83 est un nombre premier!
89 est un nombre premier!
97 est un nombre premier!Un autre possibilité, consiste à utiliser une regex.
Astuce trouvée sur http://montreal.pm.org/tech/neil_kandalgaonkar.shtml?s=09
La négation de cette regex permet de savoir si le nombre est premier.
import re
r1 = re.compile(r'^1?$|^(11+?)\1+$')
not r1.match("1"*9) # False car 9 n'est pas un nombre premier
not r1.match("1"*13) # True car 13 est un nombre premier
not r1.match("1"*32002) # False car 32002 n'est pas un nombre premier
not r1.match("1"*32003) # True car 32003 est un nombre premierIntéressant comme regex
Commentaires
Matt (non vérifié)
ven, 04/05/2018 - 22:34
Permalien
Un excellent petit exercice
Un excellent petit exercice pour réfléchir à l'optimisation du code :-)
* mettre num = int(num) en première ligne de la fonction. Ça évite de faire la conversion deux fois à chaque itérations de la boucle,
* les diviseurs d'un nombre sont forcément inférieurs ou égaux a sa moitié, donc on peut prendre la moitié du range : range(num // 2, 2, -1)
* changer le sens du range range(2, num // 2) : statistiquement, on ferra moins de tests avant de tomber sur un diviseur en allant dans ce sens, les petits diviseurs étant plus courants que les grands (exemple : si on prend 45, avec un range décroissant on va tester 22 puis 21, 20, ... et enfin 15 à la 8ème itération... avec un range croissant, on a 3 dès la 2ème itération)
Calcul des 10000 premiers nombres premiers :
* 4.7s avec le code initial,
* 1.8s avec la première modif,
* 1.4s avec la seconde modif,
* 0.5s avec les deux premières modifs,
* 0.2s en ajoutant la troisième modif.
On peut encore quasiment doubler les performances (0.11s) en excluant les nombres pairs du range :
if num > 2 and num % 2 == 0:
return False, "{:>5d} n'est pas un nombre premier!".format(num)
for x in range(3, num // 2, 2):
Mais là ça commence à être de la triche, car on doit ajouter un test spécifique pour les nombres pairs avant de lancer la boucle :-)
Et sinon, nombre premier en anglais, c'est prime number, pas first ;-)
ronan
lun, 14/05/2018 - 17:02
Permalien
Merci beaucoup
pour toutes ces améliorations
Yann (non vérifié)
mer, 18/12/2019 - 15:41
Permalien
Optimisation
En fait l'un des diviseurs d'un nombre est inférieur à sa racine carrée, pas sa moitié.
De plus, on peut ne parcourir que les entiers impairs à partir de 3.
Soit remplacer range(2, num // 2) par range(3, sqrt(num), 2) en testant éventuellement s'il est pair dès le départ. D'une part on divise le travail en deux en retirant la recherche parmi les pairs, et d'autre part on ne va que jusqu'à la racine de num.
Par exemple pour tester les diviseurs d'un nombre à deux chiffres on ne teste la divisibilité que pour 2 puis 3, 5, 7 et 9.
Par exemple 99 = 9 x 11 sera identifié comme composé à cause de 9. Il ne sera pas utile d'aller vérifier au-delà de sqrt(99). Le seul cas où on atteint cette limite de sqrt(num) c'est pour les carrés parfaits.
ronan
lun, 20/01/2020 - 12:25
Permalien
Vraiment sympa comme sujet
Ca permet d'avoir des avis différents et c'est vraiment très intéressant.
Ajouter un commentaire