Histoire des mathématiques Algorithme
crible d'Ératosthène
Algorithmeméthode pour trouver les nombres premiers
Pour comprendre
rédactionÉliminer les multiples
Le crible d'Ératosthène trouve tous les nombres premiers jusqu'à une borne fixée. On écrit les entiers à partir de \(2\), puis on conserve \(2\) et l'on raye tous ses multiples. On passe au premier entier qui n'est pas rayé, \(3\), et l'on raye à son tour ses multiples. Le processus se poursuit avec chaque premier rencontré.
S'arrêter au bon moment
Il n'est pas nécessaire de continuer indéfiniment : il suffit de traiter les nombres jusqu'à la racine carrée de la borne. Au-delà, tout nombre composé possède déjà un facteur plus petit qui a permis de le rayer. Les nombres restants sont premiers. Cette méthode simple est toujours enseignée et elle a inspiré des cribles adaptés à de très grandes listes d'entiers.
Repères historiques
- attribué à Ératosthène de Cyrène vers -240
- transmis par Nicomaque de Gérase vers 100
La figure affiche les entiers de \(2\) à \(50\), les nombres premiers restant en rouge après le criblage.
{
"boundingBox": [
-0.8,
6.2,
6.8,
-0.8
],
"axis": false,
"points": [
{
"x": 0.0,
"y": 5.1,
"name": "2",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 1.0,
"y": 5.1,
"name": "3",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 2.0,
"y": 5.1,
"name": "4",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 3.0,
"y": 5.1,
"name": "5",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 4.0,
"y": 5.1,
"name": "6",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 5.0,
"y": 5.1,
"name": "7",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 6.0,
"y": 5.1,
"name": "8",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 0.0,
"y": 4.25,
"name": "9",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 1.0,
"y": 4.25,
"name": "10",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 2.0,
"y": 4.25,
"name": "11",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 3.0,
"y": 4.25,
"name": "12",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 4.0,
"y": 4.25,
"name": "13",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 5.0,
"y": 4.25,
"name": "14",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 6.0,
"y": 4.25,
"name": "15",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 0.0,
"y": 3.4,
"name": "16",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 1.0,
"y": 3.4,
"name": "17",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 2.0,
"y": 3.4,
"name": "18",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 3.0,
"y": 3.4,
"name": "19",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 4.0,
"y": 3.4,
"name": "20",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 5.0,
"y": 3.4,
"name": "21",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 6.0,
"y": 3.4,
"name": "22",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 0.0,
"y": 2.55,
"name": "23",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 1.0,
"y": 2.55,
"name": "24",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 2.0,
"y": 2.55,
"name": "25",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 3.0,
"y": 2.55,
"name": "26",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 4.0,
"y": 2.55,
"name": "27",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 5.0,
"y": 2.55,
"name": "28",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 6.0,
"y": 2.55,
"name": "29",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 0.0,
"y": 1.7,
"name": "30",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 1.0,
"y": 1.7,
"name": "31",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 2.0,
"y": 1.7,
"name": "32",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 3.0,
"y": 1.7,
"name": "33",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 4.0,
"y": 1.7,
"name": "34",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 5.0,
"y": 1.7,
"name": "35",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 6.0,
"y": 1.7,
"name": "36",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 0.0,
"y": 0.85,
"name": "37",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 1.0,
"y": 0.85,
"name": "38",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 2.0,
"y": 0.85,
"name": "39",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 3.0,
"y": 0.85,
"name": "40",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 4.0,
"y": 0.85,
"name": "41",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 5.0,
"y": 0.85,
"name": "42",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 6.0,
"y": 0.85,
"name": "43",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 0.0,
"y": 0.0,
"name": "44",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 1.0,
"y": 0.0,
"name": "45",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 2.0,
"y": 0.0,
"name": "46",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 3.0,
"y": 0.0,
"name": "47",
"color": "#dc2626",
"size": 2,
"fixed": true
},
{
"x": 4.0,
"y": 0.0,
"name": "48",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 5.0,
"y": 0.0,
"name": "49",
"color": "#9ca3af",
"size": 2,
"fixed": true
},
{
"x": 6.0,
"y": 0.0,
"name": "50",
"color": "#9ca3af",
"size": 2,
"fixed": true
}
]
}
Dates
- decouverte
- attribué à Ératosthène de Cyrène approximative
Liens
- porte le nom de
Sources
- Wikidata CC0-1.0