Numere prime și numere compuse

Ce este un număr prim?

Orice număr natural a>=2 care are ca divizori doar pe 1 și pe el însuși.

Ce este un număr compus?

Orice număr natural nenul diferit de 1 care nu este număr prim.

Observații:

• singurul număr par prim este 2;
• numerele prime mai mici decât un număr n dat se determină cu „ciurul lui Eratostene„. Se scriu toate numerele de la 2 pană la n și apoi se elimină pe rând toți multiplii lui 2, apoi toți multiplii lui 3, apoi toți multiplii lui 5 și așa mai departe multiplii următorului număr prim pe care nu l-am eliminat încă. Ne oprim când ajungem la un număr a cărui pătrat este mai mare decât n.
• avem o infinitate de numere prime.

Teoreme importante

• Orice număr prim a>=3 este de forma 4*k+1 sau 4*k+3.
• Orice număr prim a>=5 este de forma 6*k+1 sau 6*k+5.