Nombres premiers et test de primalité~3 min
Un entier naturel $p$ est premier s'il possède exactement deux diviseurs positifs : $1$ et $p$. Ainsi $0$ et $1$ ne sont pas premiers ; $2$ est le seul premier pair. Un entier $n\geq2$ non premier est dit composé : $n=ab$ avec $1\lt a\leq b\lt n$.
1. Tout entier $n\geq2$ admet au moins un diviseur premier : le plus petit diviseur $d\gt 1$ de $n$ est premier.
Preuve : si $d$ avait un diviseur $d'$ avec $1\lt d'\lt d$, alors $d'$ diviserait $n$ et contredirait la minimalité de $d$.
2. Test de primalité. Si $n\geq2$ n'est divisible par aucun nombre premier $p$ tel que $p\leq\sqrt n$, alors $n$ est premier.
Preuve : si $n=ab$ avec $1\lt a\leq b$, alors $a^2\leq ab=n$, donc $a\leq\sqrt n$, et le plus petit diviseur premier de $a$ est un diviseur premier de $n$ inférieur ou égal à $\sqrt n$.
1. Encadrer $\sqrt n$ : trouver le plus grand premier $p\leq\sqrt n$.
2. Tester la divisibilité de $n$ par $2,3,5,7,11,\dots,p$ (critères ou division).
3. Aucun ne divise $n$ : $n$ est premier. Sinon on a un diviseur, $n$ est composé.
Exemple : $n=191$ : $13^2=169\leq191\lt 196=14^2$, donc $\sqrt{191}\lt 14$ ; premiers à tester : $2,3,5,7,11,13$.
$191$ impair ; $1+9+1=11$ non multiple de $3$ ; ne finit ni par $0$ ni par $5$ ; $191=7\times27+2$ ; $191=11\times17+4$ ; $191=13\times14+9$. $191$ est premier.
Exemple : $n=221$ : $\sqrt{221}\lt 15$ ; $2,3,5,7,11$ ne divisent pas $221$ mais $221=13\times17$ : composé.
Crible d'Ératosthène jusqu'à $50$ : on barre les multiples de $2,3,5,7$ ($7\leq\sqrt{50}\lt 8$ suffit) ; il reste les $15$ nombres premiers inférieurs à $50$.
def est_premier(n):
if n < 2:
return False
d = 2
while d * d <= n: # d <= racine de n
if n % d == 0:
return False
d = d + 1
return True
def crible(N):
premier = [True] * (N + 1) # indices 0..N
premier[0] = premier[1] = False
for p in range(2, N + 1):
if premier[p]: # p est premier :
for m in range(p * p, N + 1, p):
premier[m] = False # on barre ses multiples
return [p for p in range(N + 1) if premier[p]]
crible(50) renvoie [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]. On commence à barrer à $p^2$ : les multiples plus petits ont déjà été barrés par un premier plus petit.
L'ensemble des nombres premiers est infini.
Raisonnons par l'absurde : supposons qu'il n'y ait qu'un nombre fini de nombres premiers, $p_1,p_2,\dots,p_k$. Posons $N=p_1p_2\cdots p_k+1$.
$N\geq2$, donc $N$ admet un diviseur premier $q$ (propriété 1). Par hypothèse, $q$ est l'un des $p_i$ : $q$ divise donc le produit $p_1p_2\cdots p_k$. Comme $q$ divise aussi $N$, $q$ divise la différence $N-p_1p_2\cdots p_k=1$ : impossible pour un nombre premier ($q\geq2$).
Contradiction : il y a une infinité de nombres premiers.
Attention : $N$ n'est pas forcément premier ($2\times3\times5\times7\times11\times13+1=30031=59\times509$) ; on utilise seulement qu'il a un diviseur premier.