Comment vérifier si un nombre est premier en Python

Ce tutoriel va vous apprendre à écrire un programme Python pour vérifier si un le 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 :

• revvoir 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 revvoir les bases des nombres premiers.

En théorie des nombres, un nombre naturel n dit-on s'il a exactement deux facteurs: 1 et le numéroself (n). Rappel de vos mathématiques scolaires : un nombre i est dit être un facteur du nombre n, Si i divise n uniformément. ✅

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 numéro n en est un facteurself.

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 devez ne sauraient être capable de 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 le range() objet en Python.

En Python, range(start, stop, step) renvoie un objet plage. Vous pouvez ensuite itérerate sur l'objet de plage pour obtenir une séquence de start tout le chemin 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 for boucle.

Voici ce que nous aimerions faire :

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

• Si vous avez parcouru toute la plage de nombres de 2 tout le chemin jusqu'à n - 1 sans trouver un nombre qui divise n uniformément, 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 ça revient 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 c'est génialater que n / xnumx is n itself.

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 semble que nous ayons optimisé, cet algorithme n’est pas plus efficace que le previous en termes de complexité d’exécution. En fait, tous deux ont O (n) complexité d'exécution : 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.

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

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

If 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 approximatifatejuillet 4.24.

Et dans les facteurs qui se produisent par paires (un B), vous pouvez voir que si a est inférieur à 4.24, alors b est greater 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 parfait square, vous aurez a = b = √n comme l'un des facteurs.

▶️ Regardez les facteurs de 36 dans le tableau ci-dessous. Comme 36 est un parfait square, 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 numéro n peut s'écrire n = axb
• If n est un parfait square, puis une = b = √n.
• Et si a < b, puis, un < √n et le b > √n.
• Sinon, si un > b, puis un > √n et le b < √n.

Ainsi, au lieu de parcourir tous les entiers jusqu’à n/2, vous pouvez choisir de parcourir jusqu’à √n. Et c'est beaucoup plus efficace que notre prevapproche judicieuse.

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 le square racine d'un nombre, importons le module mathématique intégré de Python et utilisons math.sqrt() la fonction.
• As n peut ne pas être parfait square, nous devrons le convertir en entier. Utilisation int(var) jeter var dans un int.
• Pour nous assurer que nous sommes à jourally en vérifiant jusqu'à √n, nous ajoutons un plus un comme range() La fonction exclut le point de terminaison 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éonsate quelques tracés simples pour comprendre O(n) et O(√n) visually.

Comparaison de O(n) et O(√n) Visually

▶️ Exécutez l'extrait de code suivant dans un Carnet Jupyter environnement 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éerate un tableau de nombres.
• Et ensuite, nous recueillons les valeurs de n et √n jusqu'à 20 non compris, dans un pandas dataframe.
• Ensuite, nous traçons en utilisant tracé linéaire de Seaborn() la fonction.

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écapitulatif.

• 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 seul facteur de n greater que n/2 est n c'estself, 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 tutoriel sur Programmes Python sur les opérations de chaîne– où vous apprendrez à vérifier si les chaînes sont des palindromes, des anagrammes, etc.

Rendez-vous tous dans un autre tutoriel. Jusque-là, bon codage ! 👩🏽‍💻