Ciurul lui Eratostene: algoritmul pentru găsirea numerelor prime într-o listă

Teorie: Ciurul Eratostene - găsește numerele prime dintr-o listă eliminând multiplii numerelor prime mici

Matematicianul grec ERATOSTENE (275 - 194 î.Hr.) a aplicat o metodă inedită și ușoară pentru a determina dacă numerele dintr-o listă sunt prime. Pornind de la numerele prime mici cunoscute, 2, 3, 5, 7, 11, 13, 17, 21, etc. e clar că toți multiplii acestor numere prime mici nu sunt numere prime, ci compuse, un număr prim având ca divizori doar pe 1 și numărul însuși. El a ordonat crescător o listă de numere naturale din care a tăiat apoi toți multiplii acestor numere prime pentru a identifica restul numerelor prime din acea listă. Vom exemplifica această metodă pe o listă de numere ordonate crescător, de la 2 până la 100:

  • Numărul 2 este prim, vom tăia deci din acest șir toți multiplii lui 2: 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 2 × 50 = 100. 2 × 51 = 102, e mai mare decât 100, ne oprim.
  • Multiplii lui 2 de tăiat 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, 88, 90, 92, 94, 96, 98, 100 (numerele din doi în doi).
  • 3 este număr prim, deci vom tăia din listă și toți multiplii lui 3: 3 × 2 = 6 (care a fost deja tăiat din listă, fiind multiplu de 2); 3 × 3 = 9; 3 × 4 = 12 (care a fost tăiat din listă, fiind și multiplu de 2); 3 × 5 = 15; 3 × 6 = 18 (care a fost deja tăiat din listă fiind și multiplu de 2); ... și așa mai departe până la: 3 × 33 = 99. 3 × 34 = 102, e mai mare decât 100, ne oprim.
  • Multiplii lui 3 de tăiat 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 (numerele din trei în trei). Dacă eliminăm multiplii lui 2 care au fost deja tăiați din listă, rămâne să mai tăiem: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, adică exact numerele care au ca divizori doar numere prime mai mari sau egale cu 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.
  • Tot așa vom proceda și cu următorul număr prim, 5: 5 × 2 = 10 (care a fost deja tăiat din listă, fiind și multiplu de 2); 5 × 3 = 15 (care a fost deja tăiat din listă, fiind multiplu de 3); 5 × 4 = 20 (care a fost deja tăiat din listă, fiind multiplu de 2); 5 × 5 = 25; 5 × 6 = 30 (care a fost deja tăiat din listă, fiind multiplu de 2 și de 3); 5 × 7 = 35; ... și așa mai departe până la: 5 × 20 = 100 (care a fost deja tăiat din listă, fiind multiplu de 2). 5 × 21 = 105, e mai mare decât 100, ne oprim.
  • Multiplii lui 5 de tăiat din listă: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (numerele din cinci în cinci). Dacă eliminăm multiplii lui 2 și 3, care au fost deja tăiați din listă, mai rămânem să mai tăiem doar: 25, 35, 55, 65, 85, 95, adică numere care au ca divizori doar numere prime mai mari sau egale cu 5: 5 × 5 = 25; 5 × 7 = 35; 5 × 11 = 55; 5 × 13 = 65; 5 × 17 = 85; 5 × 19 = 95.
  • Apoi procedăm la fel cu următorul număr prim, 7: 7 × 2 = 14 (care a fost deja tăiat din listă, fiind și multiplu de 2); 7 × 3 = 21 (care a fost deja tăiat din listă, fiind multiplu de 3); 7 × 4 = 28 (care a fost deja tăiat din listă, fiind multiplu de 2); 7 × 5 = 35 (care a fost deja tăiat din listă, fiind și multiplu de 5); 7 × 6 = 42 (care a fost deja tăiat din listă, fiind și multiplu de 2 și de 3); ... 7 × 7 = 49; ... și așa mai departe până la: 7 × 14 = 98 (care a fost deja tăiat din listă, fiind multiplu de 2). 7 × 15 = 105, e mai mare decât 100, ne oprim.
  • Multiplii lui 7 de tăiat din listă: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98 (numerele din șapte în șapte). Dacă eliminăm din listă multiplii de 2, 3, și 5, care au fost deja tăiați din listă, mai rămâne să tăiem: 49, 77, 91, adică exact numerele care au ca divizori doar numere prime mai mari sau egale cu 7: 7 × 7 = 49; 7 × 11 = 77; 7 × 13 = 91.
  • Următorul număr prim din listă este 11 și ar trebui să tăiem din listă multiplii de 11; însă, așa cum am văzut, ar trebui să tăiem din listă doar numere care au ca divizori doar numere prime mai mari sau egale cu 11. Dar deja 11 × 11 = 121, este mai mare decât 100, înseamnă că toate numerele care au rămas în listă după procesul descris mai sus sunt deja numere prime.
  • După ce eliminăm multiplii de 2, 3, 5 și 7, mai rămân în listă: 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 de la 2 până la 100.

Ce este un număr prim?

Ce este un număr compus?

Numerele prime până la 1.000

Numerele prime până la 10.000

Ciurul lui Eratostene

Algoritmul lui Euclid

Simplificarea fracțiilor, cum se simplifică fracțiile ordinare: pași de urmat și exemple