Python: Calculer les nombres premiers

def isPrime(num):
    if str(num).isnumeric() and int(num) >= 2:
        for x in range(int(num) - 1, 1, -1):
            if int(num) % x == 0:
                return False, "{:>5d} n'est pas un nombre premier!".format(num)
        return True, "{:>5d} est un nombre premier!".format(num)
    else:
        return False, "Saisir un nombre supérieur égal à 2 !!!"

Exécution de la fonction:

for x in range(50):
    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!

Suivant les conseils de Matt, grosse amélioration de la fonction isPrime()

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

Effectivement, toutes les améliorations apportées améliorent énormément les performances de la fonction.

Analyse des performances à l'aide du module "timeit.timeit"

Avec la fonction de départ, 8,50 secondes

Avec les améliorations, 0,28 seconde

Comme quoi, il est important de développer tranquillement, sans se presser.............

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

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.