Numere prime Numere compuse Criterii de recunoastere a numerelor prime Ciurul lui Eratostene

Inca din clasa a V-a am discutat despre divizibilitatea numerelor naturale, am invatat Criteriile de divizibilitate dar divizorii unui numar sau multipli unui numar.
Astfel :
Doua numere se numesc prime daca cel mai mare divizor comun a celor doua numere este 1 .
Orice numar natural, cu exceptia lui 1, are cel putin doi divizori: pe 1 si pe el insusi.
Un numar natural care are exact doi divizori se numeste numar prim.
Exemplu:
Numerele 2, 3, 5, 7, 11, 13 sunt numere prime.
Un numar natural care re cel putin trei divizori se numeste numar compus
Exemplu:
Numerele: 4, 6, 8, 9, 10 sunt numere compuse.
Observatie
Numarul 2 este singurul numar par prim, deoarece are exact doi divizori, adica pe 1 si pe el insusi.
Numarul 1 are decat un singur divizor, deci numarul 1 nu este nici prim, nici compus.
Ciurul lui Eratostene
Ciurul lui Eratostene este un criteriu simplu si vechi, creat de Eratostene, un matematician din Grecia antica.
Acesta permite gasirea tuturor numerelor prime, mai mici sau egale cu numarul natural dat n:
Existam mai multe etape pe care trebuie sa le parcurgem pentru a gasii numerele prime
Etapele:
1. Se scriu numerele de la 2 la n intr-o lista
2. Primul numar prim este 2. Se taie cu o linie oblica toate numerele din lista care sunt multiplii lui 2. Astfel obtinem o noua lista cu numere taiate si netaiate.
3. Primul numar netaiat din lista este de asemenea prim.Se taie cu o linie oblica toate numerele din lista care sunt multiplii acestui numar. Rezulta o noua lista
4 Se repeta etapa trei pana cand noua lista nu mai contine numere netaiate.
5. Rezulta o lista finala care contine numere taiate si numere netaiate. Cele netaiate sunt toate numere prime mai mici sau egale ca n.
Exemplu
Gasiti numerele prime pana la 20

Astfel am gasit numerele prime mai mici decat 20
2, 3, 5, 7, 11, 13, 17, 19
Putem folosii acest sir pentru a afla numerele prime astfel:
- impartim numarul la numerele prime in ordine crescatoare pana cand  catul devine mai mic decat impartitorul.
- daca restul tuturor impartirilor nu este 0, atunci numarul este prim, daca in schimb restul uneia din impartiri este 0, atunci numarul este compus.