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?

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