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 premier

Intéressant comme regex

Commentaires

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

pour toutes ces améliorations

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.

Ca permet d'avoir des avis différents et c'est vraiment très intéressant.

Ajouter un commentaire

Filtered HTML

  • Les adresses de pages web et de messagerie électronique sont transformées en liens automatiquement.
  • Tags HTML autorisés : <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Les lignes et les paragraphes vont à la ligne automatiquement.

Plain text

  • Aucune balise HTML autorisée.
  • Les adresses de pages web et de messagerie électronique sont transformées en liens automatiquement.
  • Les lignes et les paragraphes vont à la ligne automatiquement.
CAPTCHA
Cette question permet de s'assurer que vous êtes un utilisateur humain et non un logiciel automatisé de pollupostage.
CAPTCHA visuel
Entrez les caractères (sans espace) affichés dans l'image.