Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą.
Najprostszy test pierwszości to metoda naiwna i wygląda następująco: dla danej liczby n należy sprawdzić, czy dzieli się ona kolejno przez 2, 3, aż do n−1. Jeśli przez żadną z nich się nie dzieli, oznacza to, że jest pierwsza.
SITO ERATOSTENESA
Ze zbioru liczb naturalnych z przedziału [2,n] tj. {2,3,4,...,n}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest {4,6,8,...}.
Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę 3 i usuwamy wszystkie jej wielokrotności większe od niej samej: {6,9,12,...}, przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.
Według tej samej procedury postępujemy dla liczby 5. Następnie dla 7, 11, 13 aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.
Wykreślanie powtarzamy do momentu, gdy liczba i, której wielokrotność wykreślamy, będzie większa niż pierwiastek z n.
Dla danej liczby n wszystkie niewykreślone liczby mniejsze, bądź równe n są liczbami pierwszymi.