Ciurul lui Eratostene: algoritm pt eliminarea multiplilor de numere prime dintr-o listă, până la o limită dată

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

Matematicianul grec ERATOSTENE (275 - 194 î.Hr.) a aplicat o metodă inedită și ușoară pentru a determina dacă numerele sunt prime sau nu.

Se scrie șirul numerelor naturale de la 2 până la 100, ordonate crescător, sub forma unei liste. Se taie din acest șir toți multiplii numerelor prime, astfel:

  • numărul 2 este prim, vom tăia deci din acest șir toți multiplii lui 2;
  • 3 este număr prim, deci vom tăia și toți multiplii lui 3;
  • tot așa vom proceda și cu 5;
  • apoi va urma 7;
  • următorul număr prim este 11; însă, deoarece 7 * 7 = 49, este mai mic decât 100 și 11 * 11 = 121, este mai mare decât 100, toate numerele care au rămas în listă după procesul descris mai sus sunt numere prime;
  • Multiplii lui 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, ... 100
  • Multiplii lui 3: 6, 9, 12, 15, 18, 21, 24, 27, ... 99
  • Multiplii lui 5: 10, 15, 20, 25, 30, 35, 40, 45, ... 100
  • Multiplii lui 7: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98
  • După ce eliminăm multiplii de 2, 3, 5 și 7, mai rămân: 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?

Ciurul lui Eratostene

Algoritmul lui Euclid

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