Comment vérifier si un nombre est premier en Python

Ce tutoriel va vous apprendre à écrire un programme Python pour vérifier si un nombre est premier ou non.

Si vous avez déjà passé des tests de codage, vous aurez rencontré la question mathématique du test de primalité ou pour vérifier si un nombre est premier. Et au cours des prochaines minutes, vous apprendrez à trouver la solution optimale à cette question.

Dans ce didacticiel, vous allez :

• revoir les bases des nombres premiers,
• écrire du code Python pour vérifier si un nombre est premier, et
• optimisez-le davantage pour obtenir un algorithme d'exécution O(√n).

Pour tout cela et plus encore, commençons.

Qu'est-ce qu'un nombre premier?

Commençons par revoir les bases des nombres premiers.

En théorie des nombres, un nombre naturel n est dit premier s'il a exactement deux diviseurs : 1 et le nombre lui-même ( n ). Rappelez-vous de vos mathématiques scolaires : un nombre i est dit être un facteur du nombre n , si i divise n de manière égale.

Le tableau suivant répertorie quelques nombres, tous leurs facteurs et s'ils sont premiers.

A partir du tableau ci-dessus, nous pouvons noter ce qui suit :

• 2 est le plus petit nombre premier.
• 1 est un diviseur de tout nombre.
• Chaque nombre n est un facteur de lui-même.

Donc 1 et n sont des facteurs triviaux pour tout nombre n. Et un nombre premier ne devrait pas avoir d'autres facteurs que ces deux.

Cela signifie que lorsque vous passez de 2 à n - 1, vous ne devriez pas pouvoir trouver un facteur non trivial qui divise n sans reste.

Algorithme O(n) pour vérifier si un nombre est premier en Python

Dans cette section, formalisons l'approche ci-dessus dans une fonction Python.

Vous pouvez parcourir tous les nombres de 2 à n - 1 en utilisant l'objet range() en Python.

En Python, range(start, stop, step) renvoie un objet range. Vous pouvez ensuite itérer sur l'objet range pour obtenir une séquence de start jusqu'à stop -1 par étapes de step .

Puisque nous avons besoin de l'ensemble des entiers de 2 à n-1, nous pouvons spécifier range(2, n) et l'utiliser en conjonction avec la boucle for .

Voici ce que nous aimerions faire :

• Si vous trouvez un nombre qui divise n uniformément sans reste, vous pouvez immédiatement conclure que le nombre n'est pas premier.

• Si vous avez parcouru toute la plage de nombres de 2 jusqu'à n - 1 sans trouver un nombre qui divise n de manière égale, alors le nombre est premier.

Fonction Python pour vérifier le nombre premier

En utilisant ce qui précède, nous pouvons continuer et définir la fonction is_prime() comme suit.

 def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True

Analysons maintenant la définition de fonction ci-dessus.

• La fonction ci-dessus is_prime() prend un entier positif n comme argument.
• Si vous trouvez un facteur dans la plage spécifiée de (2, n-1), la fonction renvoie False , car le nombre n'est pas premier.
• Et il renvoie True si vous parcourez toute la boucle sans trouver de facteur.

Ensuite, appelons la fonction avec des arguments et vérifions si la sortie est correcte.

 is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True

Dans la sortie ci-dessus, vous voyez que 2 et 11 sont premiers (la fonction renvoie True ). Et 8 et 9 ne sont pas premiers (la fonction renvoie False ).

Comment optimiser la fonction Python is_prime()

Nous pouvons faire une petite optimisation ici. Observez la liste des facteurs dans le tableau ci-dessous.

Eh bien, nous pouvons voir que le seul facteur de n supérieur à n/2 est n lui-même.

Cela signifie donc que vous n'avez pas besoin de boucler jusqu'à n - 1. Vous pouvez à la place exécuter la boucle uniquement jusqu'à n/2.

Si vous ne trouvez pas de facteur non trivial avant n/2, vous ne pouvez pas non plus en trouver un au-delà de n/2.

Modifions maintenant la fonction is_prime() pour vérifier les facteurs dans la plage (2, n/2)

 def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return True

Continuons et vérifions la sortie via quelques appels de fonction.

 is_prime(9) # False is_prime(11) # True

Même s'il peut sembler que nous avons optimisé, cet algorithme n'est pas plus efficace que le précédent en termes de complexité d'exécution. En fait, les deux ont une complexité d'exécution O(n) : proportionnelle à la valeur de n ou linéaire en n.

Peut-on faire mieux ? Oui nous pouvons!

️ Passez à la section suivante pour déterminer comment améliorer la complexité temporelle des tests de nombres premiers.

O(√n) Algorithme pour vérifier le nombre premier en Python

Il arrive que les facteurs d'un nombre apparaissent par paires.

Si a est un facteur du nombre n , alors il existe aussi un facteur b tel que axb = n , ou simplement, ab = n .

Vérifions cela à travers un exemple.

Le tableau ci-dessous montre les facteurs du nombre 18 apparaissant par paires. Vous pouvez vérifier la même chose pour quelques numéros supplémentaires si vous le souhaitez.

Notez également que √18 est d'environ 4,24.

Et dans les facteurs qui apparaissent par paires (a, b) , vous pouvez voir que si a est inférieur à 4,24, alors b est supérieur à 4,24 - dans cet exemple, (2, 18) et (3, 6).

La figure ci-dessous montre les facteurs de 18 tracés sur la droite numérique.

Si le nombre n est un carré parfait, vous aurez a = b = √n comme l'un des facteurs.

️ Regardez les facteurs de 36 dans le tableau ci-dessous. Comme 36 est un carré parfait, a = b = 6 est l'un des facteurs. Pour toutes les autres paires de facteurs (a, b), a < 6 et b > 6 sont valables.

En résumé, nous avons ce qui suit :

• Chaque nombre n peut s'écrire n = axb
• Si n est un carré parfait, alors a = b = √n .
• Et si a < b , alors, a < √n et b > √n .
• Sinon, si a > b , alors a > √n et b < √n .

Ainsi, au lieu de parcourir tous les entiers jusqu'à n/2, vous pouvez choisir d'exécuter jusqu'à √n. Et c'est beaucoup plus efficace que notre approche précédente.

Comment modifier l'algorithme is_prime() en O(√n)

Continuons à optimiser la fonction pour vérifier les nombres premiers en Python.

 import math def is_prime(n): for i in range(2,int(math.sqrt(n))+1): if (n%i) == 0: return False return True

Maintenant, analysons la définition de fonction ci-dessus :

• Pour calculer la racine carrée d'un nombre, importons le module mathématique intégré de Python et utilisons la fonction math.sqrt() .
• Comme n n'est peut-être pas un carré parfait, nous devrons le convertir en entier. Utilisez int(var) pour convertir var en un int .
• Pour nous assurer que nous vérifions réellement jusqu'à √n, nous ajoutons un plus un car la fonction range() exclut le point final de la plage par défaut.

La cellule de code ci-dessous vérifie que notre fonction is_prime() fonctionne correctement.

 is_prime(8) # False is_prime(15) # False is_prime(23) # True

Dans la section suivante, créons quelques graphiques simples pour comprendre O(n) et O(√n) visuellement.

Comparer visuellement O(n) et O(√n)

️ Exécutez l'extrait de code suivant dans un environnement de bloc-notes Jupyter de votre choix.

 import numpy as np import seaborn as sns import pandas as pd n = 20 x = np.arange(n) y1 = np.sqrt(x) y2 = x df = pd.DataFrame({"O(√n)":y1,"O(n)":y2}) sns.set_theme() sns.lineplot(data = df)

L'extrait ci-dessus montre comment vous pouvez tracer les courbes pour n et √n pour une plage de valeurs.

• Nous utilisons la fonction NumPy arange() pour créer un tableau de nombres.
• Et puis, nous collectons les valeurs de n et √n jusqu'à 20, mais non compris, dans un pandas DataFrame.
• Ensuite, nous traçons en utilisant la fonction lineplot() de seaborn.

D'après le graphique ci-dessous, nous voyons que √n est significativement plus petit que n.

Augmentons maintenant la plage jusqu'à 2000 et répétons les mêmes étapes que ci-dessus.

 import numpy as np import seaborn as sns import pandas as pd n = 2000 x = np.arange(n) y1 = np.sqrt(x) y2 = x df = pd.DataFrame({"O(√n)":y1,"O(n)":y2}) sns.set_theme() sns.lineplot(data = df) 

À partir du graphique ci-dessus, vous pouvez déduire que l'algorithme O(√n) est nettement plus rapide lorsque vous testez si un grand nombre est premier.

Voici un exemple rapide : 2377 est un nombre premier, vérifiez-le !

Alors que l'approche O(n) prendra l'ordre de 2000 étapes, l'algorithme O(√n) peut aider à arriver à la réponse en seulement 49 étapes.

Conclusion

Et c'est l'heure du petit résumé.

• Pour vérifier si un nombre est premier, l'approche naïve consiste à parcourir tous les nombres de la plage (2, n-1). Si vous ne trouvez pas de facteur qui divise n, alors n est premier.
• Comme le seul facteur de n supérieur à n/2 est n lui-même, vous pouvez choisir de n'exécuter que jusqu'à n/2.
• Les deux approches ci-dessus ont une complexité temporelle de O(n).
• Comme les facteurs d'un nombre apparaissent par paires, vous ne pouvez courir que jusqu'à √n. Cet algorithme est beaucoup plus rapide que O(n). Et le gain est appréciable lorsqu'on vérifie si un grand nombre est premier ou non.

J'espère que vous comprenez comment vérifier si un nombre est premier en Python. Dans une prochaine étape, vous pouvez consulter notre didacticiel sur les programmes Python sur les opérations sur les chaînes, où vous apprendrez à vérifier si les chaînes sont des palindromes, des anagrammes, etc.

Rendez-vous dans un autre tutoriel. D'ici là, bon codage !