Arithmétique/Annexe/Crible d'Ératosthène

Le crible des nombres premiers est une méthode relativement efficace pour trouver tous les nombres premiers inférieurs ou égaux à un nombre précis. Disons que nous voulons tous les nombres premiers inférieurs ou égaux à 50.

Premièrement, nous écrivons tous les nombres compris entre 0 et 51 dans une table comme ci-dessous

$\begin{array}{cccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 11& 12& 13& 14& 15& 16& 17& 18& 19& 20\\ 21& 22& 23& 24& 25& 26& 27& 28& 29& 30\\ 31& 32& 33& 34& 35& 36& 37& 38& 39& 40\\ 41& 42& 43& 44& 45& 46& 47& 48& 49& 50\end{array}$

On enlève 1, car il n’est pas premier.

$\begin{array}{cccccccccc}X& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 11& 12& 13& 14& 15& 16& 17& 18& 19& 20\\ 21& 22& 23& 24& 25& 26& 27& 28& 29& 30\\ 31& 32& 33& 34& 35& 36& 37& 38& 39& 40\\ 41& 42& 43& 44& 45& 46& 47& 48& 49& 50\end{array}$

Maintenant, 2 est le plus petit nombre pas encore rayé dans la table. Nous marquons 2 comme un nombre premier et nous rayons tous ses multiples 4, 6, 8, 10 ...

$\begin{array}{cccccccccc}X& 2_p& 3& X& 5& X& 7& X& 9& X\\ 11& X& 13& X& 15& X& 17& X& 19& X\\ 21& X& 23& X& 25& X& 27& X& 29& X\\ 31& X& 33& X& 35& X& 37& X& 39& X\\ 41& X& 43& X& 45& X& 47& X& 49& X\end{array}$

Maintenant, 3 est le plus petit nombre pas encore marqué. Nous marquons 3 comme un nombre premier et nous rayons tous ses multiples 6, 9, 12, 15 ...

$\begin{array}{cccccccccc}X& 2_p& 3_p& X& 5& X& 7& X& X& X\\ 11& X& 13& X& X& X& 17& X& 19& X\\ X& X& 23& X& 25& X& X& X& 29& X\\ 31& X& X& X& 35& X& 37& X& X& X\\ 41& X& 43& X& X& X& 47& X& 49& X\end{array}$

Maintenant 5 est le plus petit nombre pas encore marqué. Nous marquons 5 comme un nombre premier et nous rayons tous les multiples de 5.

$\begin{array}{cccccccccc}X& 2_p& 3_p& X& 5_p& X& 7& X& X& X\\ 11& X& 13& X& X& X& 17& X& 19& X\\ X& X& 23& X& X& X& X& X& 29& X\\ 31& X& X& X& X& X& 37& X& X& X\\ 41& X& 43& X& X& X& 47& X& 49& X\end{array}$

Maintenant 7 est le plus petit nombre pas encore marqué. Nous marquons 7 comme un nombre premier et nous rayons tous les multiples de 7.

$\begin{array}{cccccccccc}X& 2_p& 3_p& X& 5_p& X& 7_p& X& X& X\\ 11& X& 13& X& X& X& 17& X& 19& X\\ X& X& 23& X& X& X& X& X& 29& X\\ 31& X& X& X& X& X& 37& X& X& X\\ 41& X& 43& X& X& X& 47& X& X& X\end{array}$

Voilà les nombres premiers, compris entre 1 et 50, trouvés par la méthode du crible d'Ératosthène.