Liczbami pierwszymi nazywamy takie liczby naturalne, które są podzielne tylko przez samą siebie oraz przez 1. Liczbami pierwszymi (ani złożonymi) nie są 0 ani 1.

Twierdzenie:

Liczb pierwszych jest nieskończenie wiele.

Twierdzenie to zostało udowodnione przez greckiego matematyka Euklidesa w IV wieku przed naszą erą. Aby znaleźć wszystkie liczby pierwsze, które nie są większe od z góry zadanej liczby n, można się posłużyć następującym sposobem. Należy wypisać w porządku wszystkie liczby naturalne od 2 do n. Pierwsza z tych liczb jest liczbą pierwszą. Zostawiamy ją i następnie wykreślamy wszystkie liczby, które dzielą się przez dwa, a ponieważ się dzielą przez dwa to nie są pierwsze. W praktyce oznacza to, że wykreślamy wszystkie parzyste liczby. Jeśli to już zrobimy, pierwszą liczbą po 2 jest 3. Jest ona liczbą pierwszą. Zostawiamy ją i następnie wykreślamy wszystkie liczbą, które dzielą się przez 3. Po tej operacji, kolejną liczbą, która nie została wykreślona jest 5. Jest ona liczbą pierwszą, więc ją zostawiamy i wykreślamy z pozostałych wszystkie te, które dzielą się przez 5. Jeśli będziemy kontynuować to wykreślanie w ten sposób otrzymamy wszystkie liczby pierwsze mniejsze od liczby n.

Powyższa metoda nazywana jest sitem Eratostenesa. Bardziej udoskonalona jest dziś pomocna przy wyodrębnianiu wszystkich liczb pierwszych z kilkudziesięciu milionów początkowych liczb.

W dzisiejszych czasach przy pomocy szybkich komputerów znajduje się bardzo duże liczby pierwsze. W Internecie można znaleźć "Wielkie Internetowe Poszukiwanie Liczb Pierwszych Mersenne'a" (GIMPS). 

Ciekawostki: 

Liczbą pierwszą jest 2 32582657-1(odkryto ją 4 września 2006 roku). Ma ona 9 808 358 cyfr. Nazwana jest ona 38 w kolejności tzw. liczbą Mersenne'a. 

Liczba składająca się z 23 jedynek: 11111111111111111111111 jest pierwsza.

Mamy liczby pierwsze, które składają się z kolejnych cyfr.

Przykłady: 23, 67, 4567, 23456789, 1234567891, 1234567891234567891234567891.

Dwie ostatnie liczby mają cyfry ułożone w porządku cyklicznym, rosnącym, czyli po 9 występuje 1.

Mniej jest liczb pierwszych z porządkiem cyklicznym, malejącym: 43, 10987, 76543 i 1987.

Liczba 31415926535897932384626433832795028841 składająca się z początkowych 38 cyfr, które występują w rozwinięciu dziesiętnym liczby π, jest pierwsza.

Liczba 73939133 jest pierwsza, co więcej liczby otrzymywane z niej poprzez obcinanie olejnych cyfr od prawej również są pierwsze: 7393913, 739391, 73939, 7393, 739, 73, 7.