Déterminer si un nombre est premier

Fiche

Divisibilité

Soit a et b deux nombres entiers naturels.
On dit que b est un diviseur de a s'il existe un nombre entier naturel q tel que a = b × q.
On dit aussi que a est un multiple de b, ou que a est divisible par b.
Exemple : 72 est divisible par 8 (et par 9) car 72 = 8 × 9.

Nombres premiers

Un nombre entier naturel (supérieur ou égal à 2) est un nombre premier s'il admet exactement 2 diviseurs : 1 et lui-même.
Exemple : 2, 3, 5, 7, 11, 13, 17, 19 … sont des nombres premiers. Il en existe une infinité.

Remarque

Pour déterminer si un nombre entier naturel n supérieur ou égal

2 est un nombre premier, on doit chercher un diviseur de n parmi les nombres premiers successifs (2, 3, 5, 7, 11 …) jusqu'à la valeur $\sqrt{n}$ .
En effet, si n n'admet aucun diviseur parmi les nombres premiers successifs jusqu'à la valeur $\sqrt{n}$ , il n'en admettra pas non plus entre $\sqrt{n}$ et n car les diviseurs d'un nombre vont par paires : l'un compris entre 2 et $\sqrt{n}$ , et l'autre compris entre $\sqrt{n}$ et n.
Si n n'admet aucun diviseur parmi les nombres premiers successifs jusqu'à la valeur $\sqrt{n}$ , c'est donc un nombre premier.

Crible d'Ératosthène

Dans le crible d'Ératosthène, qui contient les nombres de 1 à 100, on a rayé successivement les multiples de 2, ceux de 3, ceux de 5 et ceux de 7 (11² > 100), pour obtenir la liste des nombres premiers inférieurs à 100.
1 est considéré comme n'étant pas un nombre premier.