Ciurul lui Eratostene: algoritmul folosit pentru a găsi (identifica) numerele prime dintr-o listă ordonată crescător. Se începe prin a elimina multiplii numerelor prime mai mici

Matematicianul grec ERATOSTENE (275 - 194 î.Hr.) a folosit o metodă nouă și simplă pentru acea vreme, pentru a determina dacă numerele dintr-o listă sunt sau nu prime.
A început cu binecunoscutele numere prime mai mici: 2, 3, 5, 7, 11, 13, 17, 23 etc. Este clar că toți multiplii lor nu sunt numere prime, ci compuse.
A aranjat o listă de numere naturale în ordine crescătoare. Apoi a identificat și a eliminat din ea toate numerele compuse mai mari din această listă, acelea care sunt multipli ai numere prime mici, și, astfel, a rămas în listă doar cu numerele prime mai mari din această listă.
Ilustram mai jos această metodă, cu o listă de numere sortate în ordine crescătoare, de la 2 la 100:

Numărul 2 este un număr prim, așa că mai întâi identificăm toți multiplii lui 2 din listă:
2 × 2 = 4
2 × 3 = 6
2 × 4 = 8
2 × 5 = 10
2 × 6 = 12
2 × 7 = 14
2 × 8 = 16
2 × 9 = 18
2 × 10 = 20
... și așa mai departe, până la numărul: 2 × 50 = 100.
Numărul 2 × 51 = 102, este mai mare decât 100, așa că ne putem opri.
Eliminați acum toți multiplii numărului 2 din listă: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38 , 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 86 , 90, 92, 94, 96, 98, 100.

Trecem la următorul număr prim: numărul 3 este un număr prim, așa că identificăm toți multiplii lui 3 din listă:
3 × 2 = 6 (Acest număr a fost deja eliminat din listă, este multiplu de 2);
3 × 3 = 9
3 × 4 = 12 (Acest număr a fost deja eliminat din listă, este multiplu de 2);
3 × 5 = 15
3 × 6 = 18 (Acest număr a fost deja eliminat din listă, este multiplu de 2);
... și așa mai departe, până la numărul: 3 × 33 = 99.
Numărul 3 × 34 = 102, este mai mare decât 100, așa că ne putem opri.
Eliminați acum din nou toți multiplii numărului 3 din listă: 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57 , 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99.
Dacă am eliminat deja toți multiplii numărului 2 din listă, ne rămân de eliminat doar: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. Aceste numere sunt scrise mai jos, ca multipli ai numărul 3:
3 × 3 = 9
3 × 5 = 15
3 × 7 = 21
3 × 9 = 3 × 3 × 3 = 27
3 × 11 = 33
3 × 13 = 39
3 × 15 = 3 × 3 × 5 = 45
3 × 17 = 51
3 × 19 = 57
3 × 21 = 3 × 3 × 7 = 63
3 × 23 = 69
3 × 25 = 3 × 5 × 5 = 75
3 × 27 = 3 × 3 × 3 × 3 = 81
3 × 29 = 87
3 × 31 = 93
3 × 33 = 3 × 3 × 11 = 99.

Procedăm apoi la fel cu următorul număr prim, 5:
5 × 2 = 10 (Acest număr a fost deja eliminat din listă - este multiplu de 2);
5 × 3 = 15 (Acest număr a fost deja eliminat din listă - este multiplu de 3);
5 × 4 = 20 (Acest număr a fost deja eliminat din listă - este un multiplu de 2);
5 × 5 = 25
5 × 6 = 30 (Acest număr a fost deja eliminat din listă - este multiplu de 2 și 3);
5 × 7 = 35
... și așa mai departe, până la numărul: 5 × 20 = 100 (Acest număr a fost deja eliminat din listă - este un multiplu de 2).
Numărul 5 × 21 = 105, este mai mare decât 100, așa că ne putem opri.
Eliminăm toți multiplii numărului 5 din listă: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
Dacă am eliminat deja multiplii lui 2 și 3 din listă, mai rămânem cu următoarele numere de eliminat: 25, 35, 55, 65, 85, 95, adică exact acele numere care au în descompunerea lor doar factori primi mai mari sau egali cu 5:
5 × 5 = 25
5 × 7 = 35
5 × 11 = 55
5 × 13 = 65
5 × 17 = 85
5 × 19 = 95.

Continuăm procesul cu următorul număr prim 7:
7 × 2 = 14 (numărul a fost deja eliminat din listă - este multiplu de 2);
7 × 3 = 21 (numărul a fost deja eliminat din listă - este multiplu de 3);
7 × 4 = 28 (numărul a fost deja eliminat din listă - este multiplu de 2);
7 × 5 = 35 (numărul a fost deja eliminat din listă - este multiplu de 5);
7 × 6 = 42 (numărul a fost deja eliminat din listă - este multiplu de 2 și 3);
7 × 7 = 49
... și așa mai departe, până la numărul: 7 × 14 = 98 (numărul a fost deja eliminat din listă - este un multiplu de 2).
7 × 15 = 105, este mai mare decât 100, așa că ne putem opri.
Eliminăm toți multiplii numărului 7 din listă: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
Dacă nu ne uităm la multiplii lui 2, 3 și 5, care au fost deja eliminați din listă, mai trebuie să eliminăm doar: 49, 77, 91. Acestea sunt tocmai numerele care au în descompunere factori primi care sunt mai mari sau egali cu 7:
7 × 7 = 49
7 × 11 = 77
7 × 13 = 91.

Următorul număr prim din listă este 11 și ar trebui să eliminăm multiplii lui 11.
Totuși, așa cum am văzut în pașii de mai sus, ar trebui să încercăm să eliminăm din listă doar numerele care au în descompunere factori primi care sunt mai mari sau egali cu 11.
Dar deja 11 × 11 = 121, care este mai mare decât 100.
Aceasta înseamnă că toate numerele care au rămas în listă după efectuarea pașilor de mai sus sunt deja numere prime.

Lista de numere prime este formată din numerele neeliminate.
După eliminarea din listă a tuturor multiplilor numerelor prime 2, 3, 5 și 7, rămânem în listă cu aceste numere: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 - adică exact lista numerelor prime dela 2 până la 100.

ro.numere-prime.ro