Badanie, czy liczba jest pierwsza.

Liczba pierwsza 

– liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą.

Zbiór wszystkich liczb pierwszych oznacza się symbolem . Liczby naturalne większe od 1, które nie są pierwsze, nazywa się liczbami złożonymi. Z podanych definicji wynika, że liczby 0 i 1 nie są ani pierwsze, ani złożone.

Podstawowe własności: 

• Najmniejszy różny od jedynki dzielnik naturalny liczby naturalnej, większej od jedności, jest liczbą pierwszą.
• Euklides pokazał, że żaden skończony zbiór nie zawiera wszystkich liczb pierwszych:

Niech X będzie skończonym zbiorem liczb pierwszych. Niech x będzie iloczynem wszystkich liczb występujących w X (gdy X jest puste, to x=1). Jedynym wspólnym dzielnikiem liczb x oraz x+1 jest 1. Zatem żadna liczba pierwsza, występująca w X, nie jest dzielnikiem liczby x+1. Ale x+1 > 1. Więc x+1 ma dzielnik p, który jest liczbą pierwszą. Liczba pierwsza p nie należy do X (bo jest dzielnikiem liczby x+1).

• Każda liczba naturalna większa od 1 daje się jednoznacznie zapisać w postaci iloczynu skończonego niemalejącego ciągu pewnych liczb pierwszych. Twierdzenie to był w stanie udowodnić już Euklides (stworzył niezbędne narzędzia), ale uczynił to dopiero Gauss. Twierdzenie to oznacza, że liczby pierwsze są w pewnym sensie atomami, z których przy pomocy mnożenia zbudowane są pozostałe liczby.

Wyznaczanie

Aby znaleźć wszystkie liczby pierwsze w zadanym przedziale liczbowym, można posłużyć się algorytmem zwanym sitem Eratostenesa: jeśli liczba naturalna N większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka zN, to N jest liczbą pierwszą.

Schemat blokowy sprawdzający czy liczba jest pierwsza