ciurul lui eratostene

CIURUL LUI ERATOSTENE

In matematică, ciurul lui Eratostene este un algoritm simplu și vechi de descoperire a tuturor numerelor prime până la un întreg specificat.

Algoritm:

1. Se scrie o listă a numerelor de la 2 la cel mai mare număr ce urmează a fi testat pentru primalitate. Numim această listă: lista A.

2. Se trece numărul 2, primul număr prim găsit, într-o altă listă, cea a numerelor prime găsite. Numim această listă: lista B.

3. Se marchează 2 și toți multiplii lui 2 din lista A.4. Primul număr nemarcat din listă este un număr prim. Se trece acest

număr în lista B.5. Se marchează acest număr și toți multiplii lui din lista A. Marcarea de

multipli poate să înceapă de la pătratul numărului, întrucât multiplii mai mici au fost deja marcați în pașii anteriori.

6. Se repetă pașii 4 și 5 până când se epuizează toate numerele din lista A.

Numere prime pana la 100:

2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.