Publié le jeudi 09 juillet 2020
Modifié le dimanche 04 avril 2021 à 15h33 3 min
Modifié le dimanche 04 avril 2021 à 15h33 3 min
Déterminer si un nombre est premier
Définition : un nombre premier est un nombre entier naturel qui a exactement deux diviseurs : \(1\) et lui-même. \(1\) n'est ainsi pas un nombre premier puisqu'il n'a qu'un diviseur.
Remarque : \(1\) n'est pas premier car il n'a qu'un seul diviseur.
Pour vérifier si un nombre est premier on peut donc chercher tous les diviseurs de ce nombre, mais il existe une méthode plus facile.En effet il est inutile d'essayer de diviser par des nombres non-premiers : si un nombre n'est pas divisible par \(3\) il n'est pas divisible par \(9\) non plus. De plus, on peut se limiter aux nombres compris entre \(1\) et la racine du nombre.
Exemples :
Déterminer si \(27\) est premier.
La racine de \(27\) est comprise entre \(5\) et \(6\) car \(25\leqslant27\leqslant36\). Il suffit donc de tester les nombre premiers jusqu'à \(5\), donc \(2\); \(3\) et \(5\).
\(\frac{27}{2} = 13,5\) (pas entier, donc on continue)
\(\frac{27}{3} = 9\) (entier, donc \(3\) divise \(27\))
\(3\) est un diviseur de \(27\), donc \(27\) n'est pas premier.
La racine de \(27\) est comprise entre \(5\) et \(6\) car \(25\leqslant27\leqslant36\). Il suffit donc de tester les nombre premiers jusqu'à \(5\), donc \(2\); \(3\) et \(5\).
\(\frac{27}{2} = 13,5\) (pas entier, donc on continue)
\(\frac{27}{3} = 9\) (entier, donc \(3\) divise \(27\))
\(3\) est un diviseur de \(27\), donc \(27\) n'est pas premier.
Déterminer si \(37\) est premier.
La racine de \(37\) est comprise entre \(6\) et \(7\) car \(36\leqslant37\leqslant49\). Il suffit donc de tester les nombres premiers jusqu'à \(6\), donc \(2\); \(3\) et \(5\).
\(\frac{37}{2} = 18,5\)
\(\frac{37}{3} = 12,333…\)
\(\frac{37}{5} = 7,4\)
Il n'y a donc pas de diviseur de \(37\) jusqu'à \(\sqrt{37}\), donc \(37\) est un nombre premier.
La racine de \(37\) est comprise entre \(6\) et \(7\) car \(36\leqslant37\leqslant49\). Il suffit donc de tester les nombres premiers jusqu'à \(6\), donc \(2\); \(3\) et \(5\).
\(\frac{37}{2} = 18,5\)
\(\frac{37}{3} = 12,333…\)
\(\frac{37}{5} = 7,4\)
Il n'y a donc pas de diviseur de \(37\) jusqu'à \(\sqrt{37}\), donc \(37\) est un nombre premier.
Voici une fonction en Python qui détermine si un entier est premier :
PYTHON
def est_premier(n):
if n <= 1 : #si n est négatif ou égal à 1, il n'est pas premier
return False
elif n == 2 : #2 est premier
return True
for i in range(2, round(n**0.5)+1): #on parcourt les entiers de 2 jusqu'à la racine de n (arrondie à l'entier supérieur)
#on a ajouté 1 pour que la racine soit comprise dans les diviseurs testés
if n%i == 0 : #si n est divisible par i alors n n'est pas premier
return False
return True #si on arrive jusqu'ici alors c'est que n est un nombre premier
if n <= 1 : #si n est négatif ou égal à 1, il n'est pas premier
return False
elif n == 2 : #2 est premier
return True
for i in range(2, round(n**0.5)+1): #on parcourt les entiers de 2 jusqu'à la racine de n (arrondie à l'entier supérieur)
#on a ajouté 1 pour que la racine soit comprise dans les diviseurs testés
if n%i == 0 : #si n est divisible par i alors n n'est pas premier
return False
return True #si on arrive jusqu'ici alors c'est que n est un nombre premier
retour vers la liste d'articles