$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Crible d'Eratosthène

  Le crible d'Eratosthène est une méthode (un algorithme) pour déterminer tous les nombres premiers plus petits qu'un entier donné. Voici comment procéder si on souhaite par exemple déterminer tous les entiers premiers plus petits que 100. On écrit tous les entiers qui vont de 2 à 100 (rappelons que 1 n'est pas premier). Le premier entier écrit est 2. Il est premier : on l'entoure, et on barre tous ses multiples. Le premier entier non barré après 2 est 3 : il est premier, et on barre tous ses multiples. Le premier entier non barré après 3 est 5 : il est premier et on barre tous ses multiples. Et on procède comme ceci jusqu'à épuiser tous les entiers.... Ceux qui ne sont pas barrés sont exactement les premiers!

  Voici un exemple pour déterminer tous les premiers de 1 à 40 :



Voici comment Nicomaque de Gérase, lui-même mathématicien et philosophe, vivant environ un siècle après Eratosthène (entre 200 et 100 av J-C), rapporte la méthode du crible dans son Introduction à l'arithmétique : "La méthode du crible est la suivante : j'énumère tous les nombres impairs, dans l'ordre, à partir de 3, dans une suite aussi longue que possible, et commençant avec le premier j'examine ceux qu'il peut mesurer. Je vois qu'il peut mesurer les termes qui en laissent deux entre eux, aussi loin qu'on aille.[...] Alors, prenant un nouveau départ, je vais au second nombre et j'examine ceux qu'il peut mesurer. Je vois qu'il peut mesurer les termes qui en laissent quatre entre eux.[...] Si tu marques les nombres avec des signes, tu trouveras [...] que certains échappent entièrement à la mesure par quelque nombre que ce soit, alors que d'autres sont mesurés par un seul nombre, et d'autres encore par deux ou plus...". Source : Les géomètres de la Grèce antique, Les Génies de La Science, Novembre 2004-Février 2005.
Consulter aussi...