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 :

  • 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.

What is a Prime Number?

Commençons par revoir 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 nombre lui-même (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.

nFacteursEst-ce que Premier ?
11Non
21, 2Oui
31, 3Oui
41, 2, 4Non
71, 7Oui
151, 3, 5, 15Non

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 est un facteur en soi.

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 pas être capable de trouver un facteur non trivial qui divise n sans reste.

O(n) Algorithm to Check if a Number is Prime in 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 de plage. Vous pouvez ensuite parcourir l'objet de plage pour obtenir une séquence à partir 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édiatement 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.

Python Function to Check for Prime Number

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

How to Optimize the Python Function is_prime()

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

Numéro Facteurs
61, 2, 36
101, 2, 510
181, 2, 3, 6, 918

Eh bien, nous pouvons voir que le seul facteur de n qui est supérieur à n / xnumx is n elle-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, tous les 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.

O(√n) Algorithm to Check for Prime Number in 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 d'environ 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 supérieur à 4.24 - dans cet exemple, (2, 18) et (3, 6).

ab
118
29
36
Facteurs de 18 par paires

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

facteurs sur ligne 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.

ab
136
218
312
49
66
Facteurs de 36 par paires

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

  • Chaque numéro n peut s'écrire n = axb
  • If n est un carré parfait, alors une = b = √n.
  • Et si a < b, puis, un < √n et b > √n.
  • Sinon, si un > b, puis un > √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 math.sqrt() la fonction.
  • As n n'est peut-être pas un carré parfait, nous devrons le transformer en entier. Utiliser int(var) jeter var dans un int.
  • Pour nous assurer que nous vérifions réellement 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éons quelques graphiques simples pour comprendre O(n) et O(√n) visuellement.

Comparing O(n) and 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éer 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.

vérification des nombres premiers en python

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)
vérification des nombres premiers en python

À 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 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 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 ! 👩🏽‍💻