Nombres premiers. Crible d’Ératosthène


1. Définitions et premières propriétés

Définition 1.
Soit $p$ un nombre entier naturel supérieur ou égal à $2$.
On dit que $p$ est un nombre premier lorsqu’il n’admet pas d’autres diviseurs positifs que $1$ et lui-même.
Autrement dit : Un nombre entier naturel $p$, supérieur ou égal à 2 est dit premier
lorsqu’il admet exactement deux diviseurs positifs, $1$ et lui-même.

Cette définition exclut le nombre $1$ ; donc $1$ n’est pas un nombre premier car $1$
admet exactement un seul diviseur : $1$ qui n’est autre que lui-même.

La convention que « $1$ n’est pas premier » provient du théorème d’Euclide sur l’unicité de la décomposition en facteurs premiers à l’ordre près de tout entier supérieur ou égal à $2$.

Définition 2.
Soit $n$ un nombre entier naturel supérieur ou égal à $2$.
Si $n$ n’est pas un nombre premier, on dit qu’i est composé.

Exemples

$2$ ; $3$ ; $5$ ; $7$ ; $11$ sont des nombres premiers. $6$ est un nombre composé.

2. Propriétés des nombres premiers

Propriété 1.
Pour tout entier naturel $p$, les multiples de $p$, strictement supérieurs à cet entier, ne sont pas premiers

Démonstration
Soit $p$ un entier naturel et $n$ un multiple strict de $p$.
Par définition, il existe un entier $k>1$ tel que $n = kp$. Alors $n$ admet au moins $4$ diviseurs : $1$, $k$, $p$ et $n$. Donc $n$ n’est pas premier. CQFD. $\blacktriangle$

2. Comment déterminer si un entier est premier ?

2.1. Un algorithme

1°) Une première technique consiste à utiliser un algorithme ou un programme sur
calculatrice ou un ordinateur. Pour chaque entier $N$ saisi, on crée une boucle qui teste
la divisibilité de $N$ par tous les entiers non nuls qui le précèdent.
Pour cela il suffit « pour (tous les entiers) $k$ allant de $1$ à $N$ », de calculer $N/k$, et de
vérifier si le quotient $N/k$ est entier, c’est-à-dire « si $N/k = E(N/k)$ » où $E$ désigne la partie entière d’un nombre réel. Cette fonction existe sur toutes les calculatrices programmables ! A vous de jouer.

ALGORITHME
Entrée
N est un entier supérieur ou égal à 2
Pour K allant de 2 à N faire
Affecter à Q la valeur N/K
Si Q est un entier
Alors Afficher K
Stopper le programme
Fin Si
Fin Pour
Sortie Afficher N

PROGRAMME TEXAS INSTRUMENT
: Prompt N
: For(K,2,Int(N))
: N/K$\rightarrow$Q
: If Q=Int(Q)
: Then Disp K
: Disp N/K
: Stop
: End
: End
: Disp N

PROGRAMME CASIO
”N” :?$\rightarrow$N
For 2$\rightarrow$K To Intg(N)
N:K$\rightarrow$Q
If Q=Intg(Q)
Then K
Stop
IfEnd
Next
N


2.2. Crible d’Ératosthène

2°) Nous connaissons une méthode, vielle de plusieurs siècles, appelée méthode des
cribles
, pour déterminer tous les nombres premiers compris entre $1$ et un entier
naturel $N$ quelconque, donné.

Exemple

Exercice résolu n°1.
Comment déterminer tous les nombres premiers compris entre 1 et 100 ?

Le crible d’Ératosthène [Mathématicien grec 284-192 avant J.C.]

Cette méthode permet de déterminer la liste de tous les nombres premiers inférieurs à
un nombre entier donné $N$. Cette méthode se base sur la propriété suivante
fondamentale suivante :

Méthode du crible d’Eratosthène :

On construit un tableau comportant les entiers compris entre $2$ et $N$. On conserve
chaque premier nombre rencontré et on raye tous ses ses multiples stricts dans
l’ordre croissant. Les nombres entiers non rayés sont donc premiers.