Numerele pozitive întregi care nu se divid decât cu ele însele și cu 1, se numesc numere prime.

Un număr compus este un întreg pozitiv care are cel puțin un divizor diferit de 1 și de numărul însuși. Un număr compus este deci orice număr pozitiv mai mare decât 1, care nu este număr prim.

• 2 este divizibil doar cu 2 și cu 1, deci 2 este număr prim
• 3 este divizibil doar cu 3 și cu 1, deci 3 este număr prim
• 5 este divizibil doar cu 5 și cu 1, deci 5 este număr prim
• 13 este divizibil doar cu 13 și cu 1, deci 13 este număr prim

1 nu este considerat număr prim, așa că lista numerelor prime începe cu numărul 2.

Teoria fundamentală a aritmeticii spune că orice întreg mai mare decât 1 poate fi scris ca produsul unic a unu sau mai multe numere prime, mai puțin ordinea factorilor primi. Numerele prime pot fi așadar considerate ca fiind blocurile de bază pentru toate celelalte numere. Dacă 1 ar fi considerat număr prim, numărul 15, de exemplu, ar putea fi descompus în două moduri diferite, ca 3 × 5 și ca 1 × 3 × 5; aceste două reprezentări ar fi considerate ca descompuneri diferite ale numărului 15 în numere prime, iar enunțul teoremei de mai sus ar trebui să fie modificat.

• 4 este divizibil cu 4, 2 și 1, deci 4 nu este număr prim, este un număr compus; 4 = 2²
• 6 este divizibil cu 6, 3, 2 și 1, deci 6 nu este un număr prim, este un număr compus; 6 = 2 × 3
• 8 este divizibil cu 8, 4, 2 și 1, deci 8 nu este un număr prim, este un număr compus; 8 = 2³
• 9 este divizibil cu 9, 3, și 1, așadar 9 nu este un număr prim, este un număr compus; 9 = 3²

Exemple de numere prime, până la 100: 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

EUCLID (300 î.Hr.) a demonstrat că tot așa cum mulțimea numerelor naturale sau întregi este infinită, tot așa și mulțimea numerelor prime este infinită, nu există un cel mai mare număr prim.

Nu există nicio formulă pe care să o aplicăm astfel încât să putem separa mulțimea numerelor prime de cea a numerelor compuse.