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’il 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 à $p$, ne sont pas premiers. Donc, ce sont des nombres composés.

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$

3. Crible d’Ératosthène

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.

Crible d’Ératosthène

Conclusion. La liste des nombres premiers inférieurs à 100 est :
$\mathcal L={}${2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31 ; 37 ; 41 ; 43 ; 47 ; 53 ; 59 ; 61 ; 67 ; 71 ;
73 ; 79 ; 83 ; 89 et 97}

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

A l’aide d’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

Vues : 458