En utilisant la propriété des diviseurs des nombres premiers, écrire une fonction Python qui permet de vérifier si un entier \verb/n/ est premier.
Qu'est-ce qu'un nombre premier ?
Un nombre premier est un entier naturel qui possède exactement deux diviseurs distincts entiers et positifs. Ces deux diviseurs sont 1 et le nombre, puisque tout nombre a pour diviseurs 1 et lui-même. Les nombres premiers étant ceux qui n'en possèdent aucun autre.
Un nombre premier n'est donc divisible que par 1 et par lui-même.
Quelle condition en Python permet de vérifier qu'un entier n est divisible par k ?
Pour vérifier qu'un entier n est divisible par k , on peut regarder le reste de la division euclidienne de n par k . En Python, on calcule le reste avec l'opérateur modulo \% : n\%k .
La condition qui permet de vérifier que ce reste vaut bien zéro est donc n\%k == 0 .
Comment vérifier qu'un entier n > 2 est premier ?
Un nombre premier n'est divisible que par 1 et par lui-même.
Il faut donc vérifier que n n'est divisible par aucun nombre entre 2 et n-1 .
Quelle fonction Python permet de vérifier qu'un entier n est premier ?
On définit une fonction \verb/is_prime(n)/ qui permet de vérifier qu'un entier n est premier.
On vérifie d'abord que le nombre n'est pas égal à 2, sinon on renvoie la valeur \verb/True/.
Sinon, on définit une variable \verb/is_prime = True/ qui sera mise à jour à \verb/False/ si l'on trouve un diviseur de n entre 2 et n-1 .
Ainsi, on parcourt à l'aide d'une boucle \verb/for/ tous les entiers entre 2 et n -1 et on calcule le reste de la division entre n et i à l'aide de l'opérateur modulo. Dès qu'un diviseur de n est trouvé, on quitte la boucle à l'aide de l'instruction \verb/break/.
La fonction Python qui permet de vérifier qu'un entier n est premier est donc :
\verb/ def is_prime(n): /
\verb/ is_prime = True /
\verb/ for i in range(2, n): /
\verb/ if n\%i > 0: /
\verb/ is_prime = False /
\verb/ break /
\verb/ return is_prime /