Ce guide vous expliquera comment développer un programme Python capable de déterminer si un nombre donné est premier.
Si vous avez déjà participé à des évaluations de codage, vous avez probablement rencontré le problème mathématique consistant à tester la primalité, ou à vérifier si un nombre est premier. Dans les prochaines minutes, vous allez découvrir comment trouver la solution la plus efficace à cette question.
Dans ce tutoriel, vous allez :
- revoir les notions fondamentales relatives aux nombres premiers,
- écrire un code Python pour tester si un nombre est premier, et
- l’optimiser afin d’obtenir un algorithme avec une complexité temporelle de O(√n).
Pour explorer tout cela et bien plus, commençons sans plus tarder.
Qu’est-ce qu’un nombre premier ?
Commençons par un rappel des bases concernant les nombres premiers.
En théorie des nombres, un nombre entier naturel ‘n’ est considéré comme premier s’il possède exactement deux diviseurs distincts : 1 et le nombre lui-même (‘n’). Rappelez-vous vos cours de mathématiques : un nombre ‘i’ est un facteur du nombre ‘n’ si ‘i’ divise ‘n’ sans reste. ✅
Le tableau ci-dessous présente quelques nombres, leurs facteurs respectifs et indique s’ils sont premiers ou non.
| n | Facteurs | Est premier ? |
| 1 | 1 | Non |
| 2 | 1, 2 | Oui |
| 3 | 1, 3 | Oui |
| 4 | 1, 2, 4 | Non |
| 7 | 1, 7 | Oui |
| 15 | 1, 3, 5, 15 | Non |
En observant le tableau précédent, on peut remarquer ce qui suit :
- 2 est le plus petit nombre premier.
- 1 est un diviseur de tous les nombres.
- Chaque nombre ‘n’ est un facteur de lui-même.
Ainsi, 1 et ‘n’ sont des facteurs évidents pour tout nombre ‘n’. Un nombre premier ne doit avoir aucun autre facteur que ces deux-là.
Cela signifie que lors du parcours des nombres de 2 à ‘n’ – 1, vous ne devriez pas trouver de facteur non trivial qui divise ‘n’ sans laisser de reste.
Algorithme O(n) pour tester si un nombre est premier en Python
Dans cette section, nous allons formaliser l’approche décrite ci-dessus dans une fonction Python.
Vous pouvez parcourir tous les nombres allant de 2 à ‘n’ – 1 en utilisant l’objet ‘range()’ en Python.
En Python, ‘range(début, fin, pas)’ renvoie un objet de type ‘range’. Vous pouvez ensuite itérer sur cet objet pour obtenir une séquence allant du début jusqu’à la fin-1, avec un incrément donné par ‘pas’.
Puisque nous avons besoin de l’ensemble des entiers allant de 2 à ‘n’-1, nous pouvons utiliser ‘range(2, n)’ en combinaison avec une boucle ‘for’.
Voici ce que nous allons faire :
- Si nous rencontrons un nombre qui divise ‘n’ uniformément (sans reste), nous pouvons immédiatement conclure que le nombre ‘n’ n’est pas premier.
- Si nous avons parcouru toute la plage de nombres de 2 jusqu’à ‘n’ – 1 sans trouver de nombre qui divise ‘n’ de manière exacte, alors le nombre est premier.
Fonction Python pour vérifier la primalité d’un nombre
En utilisant les principes énoncés ci-dessus, nous pouvons définir la fonction ‘est_premier()’ comme suit.
def est_premier(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Analysons maintenant la définition de cette fonction :
- La fonction ‘est_premier()’ prend un entier positif ‘n’ comme argument.
- Si nous trouvons un facteur dans la plage spécifiée (2, n-1), la fonction renvoie ‘False’, car le nombre ‘n’ n’est pas premier.
- La fonction renvoie ‘True’ si nous parcourons toute la boucle sans trouver de facteur.
Maintenant, appelons la fonction avec différents arguments pour vérifier si la sortie est correcte.
est_premier(2)
# True
est_premier(8)
# False
est_premier(9)
# False
est_premier(11)
# True
Dans la sortie ci-dessus, on peut voir que 2 et 11 sont premiers (la fonction renvoie ‘True’), tandis que 8 et 9 ne le sont pas (la fonction renvoie ‘False’).
Comment optimiser la fonction Python ‘est_premier()’ ?
Il est possible d’apporter une légère optimisation ici. Observons la liste des facteurs dans le tableau ci-dessous.
| Nombre | Facteurs |
| 6 | 1, 2, 3, 6 |
| 10 | 1, 2, 5, 10 |
| 18 | 1, 2, 3, 6, 9, 18 |
On peut constater que le seul facteur de ‘n’ qui soit supérieur à ‘n’/2 est ‘n’ lui-même.
Cela signifie que nous n’avons pas besoin de parcourir les nombres jusqu’à ‘n’ – 1. Nous pouvons nous contenter de parcourir la boucle jusqu’à ‘n’/2.
Si nous ne trouvons pas de facteur non trivial avant ‘n’/2, il est certain qu’il n’y en aura pas au-delà de ‘n’/2.
Modifions maintenant la fonction ‘est_premier()’ pour qu’elle vérifie les facteurs dans la plage (2, n/2).
def est_premier(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Vérifions à nouveau le résultat via quelques appels de la fonction.
est_premier(9)
# False
est_premier(11)
# True
Même s’il semble que nous ayons 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 de O(n) : elle est proportionnelle à la valeur de ‘n’, ou linéaire en ‘n’.
Pouvons-nous faire mieux ? Oui, c’est possible !
▶️ Passez à la section suivante pour découvrir comment améliorer la complexité temporelle des tests de nombres premiers.
Algorithme O(√n) pour tester la primalité d’un nombre en Python
Il s’avère que les facteurs d’un nombre apparaissent par paires.
Si ‘a’ est un facteur du nombre ‘n’, alors il existe également un facteur ‘b’ tel que a x b = n, ou simplement ab = n.
Vérifions cela à travers un exemple.
Le tableau ci-dessous montre les facteurs du nombre 18, qui apparaissent par paires. Vous pouvez vérifier cela avec d’autres nombres si vous le souhaitez.
Notez également que √18 est d’environ 4,24.
Dans les paires de facteurs (a, b), si ‘a’ est inférieur à 4,24, alors ‘b’ est supérieur à 4,24, comme on peut le voir dans cet exemple avec les paires (2, 18) et (3, 6).
Facteurs de 18 par paires
La figure ci-dessous illustre les facteurs de 18 placés sur une droite numérique.
Si le nombre ‘n’ est un carré parfait, nous aurons a = b = √n comme l’un des facteurs.
▶️ Examinez 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), nous avons a < 6 et b > 6.
Facteurs de 36 par paires
En résumé, nous avons les points suivants :
- Tout nombre ‘n’ peut être exprimé sous la forme n = a x b
- Si ‘n’ est un carré parfait, alors a = b = √n.
- Si a < b, alors a < √n et b > √n.
- Sinon, si a > b, alors a > √n et b < √n.
Par conséquent, au lieu de parcourir tous les entiers jusqu’à n/2, nous pouvons nous contenter d’itérer jusqu’à √n. Cette méthode est beaucoup plus efficace que notre approche précédente.
Comment modifier l’algorithme ‘est_premier()’ en O(√n)
Poursuivons l’optimisation de notre fonction pour tester la primalité des nombres en Python.
import math
def est_premier(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Analysons maintenant la définition de cette fonction :
- Pour calculer la racine carrée d’un nombre, nous importons le module math intégré de Python et utilisons la fonction ‘math.sqrt()’.
- Comme ‘n’ n’est pas nécessairement un carré parfait, nous devons le convertir en entier. Nous utilisons ‘int(var)’ pour convertir la variable ‘var’ en entier.
- Pour nous assurer que nous testons bien jusqu’à √n, nous ajoutons un ‘+ 1’, car la fonction ‘range()’ exclut par défaut la borne supérieure de l’intervalle.
L’extrait de code ci-dessous vérifie que notre fonction ‘est_premier()’ fonctionne correctement.
est_premier(8)
# False
est_premier(15)
# False
est_premier(23)
# True
Dans la section suivante, nous allons créer quelques graphiques simples pour comparer visuellement les complexités O(n) et O(√n).
Comparaison visuelle de O(n) et O(√n)
▶️ Exécutez l’extrait de code suivant dans un environnement Jupyter Notebook 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 tracer les courbes de ‘n’ et de √n pour une plage de valeurs donnée.
- Nous utilisons la fonction ‘NumPy arange()’ pour créer un tableau de nombres.
- Ensuite, nous stockons les valeurs de ‘n’ et √n jusqu’à 20 (exclu) dans un pandas DataFrame.
- Enfin, nous traçons le graphique à l’aide de la fonction lineplot() de Seaborn.
D’après le graphique ci-dessous, nous pouvons constater que √n est significativement plus petit que n.
Augmentons maintenant la plage jusqu’à 2000 et répétons les mêmes étapes que précédemment.
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)
Le graphique ci-dessus démontre clairement que l’algorithme O(√n) est beaucoup plus rapide lorsque nous testons si un grand nombre est premier.
Par exemple, 2377 est un nombre premier, vous pouvez le vérifier ! 😀
Alors que l’approche O(n) nécessiterait environ 2000 étapes, l’algorithme O(√n) peut arriver à la réponse en seulement 49 étapes. ✅
Conclusion
⏳ C’est le moment du récapitulatif.
- Pour tester la primalité d’un nombre, l’approche naïve consiste à parcourir tous les nombres de la plage (2, n-1). Si nous ne trouvons aucun facteur qui divise ‘n’, alors ‘n’ est premier.
- Comme le seul facteur de ‘n’ supérieur à ‘n’/2 est ‘n’ lui-même, nous pouvons nous contenter de ne parcourir les nombres que jusqu’à ‘n’/2.
- Les deux approches mentionnées ci-dessus ont une complexité temporelle de O(n).
- Étant donné que les facteurs d’un nombre apparaissent par paires, nous pouvons nous contenter de parcourir les nombres jusqu’à √n. Cet algorithme est beaucoup plus rapide que O(n). Le gain en efficacité est particulièrement visible lors du test de nombres très grands.
J’espère que ce tutoriel vous a permis de comprendre comment vérifier si un nombre est premier en Python. Dans une prochaine étape, vous pouvez consulter notre tutoriel sur les programmes Python liés aux opérations sur les chaînes, dans lequel vous apprendrez à vérifier si des chaînes sont des palindromes, des anagrammes, etc.
À bientôt dans un autre tutoriel. En attendant, bon codage !👩🏽💻