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 (dla liczb naturalnych w ogóle), 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, nazywanym często sitem Eratostenesa.
Algorytm ten przebiega w sposób następujący: jeśli liczba naturalna większa od 1 nie jest podzielna przez żadną z liczb pierwszych nie większych od pierwiastka z to z tego wnioskujemy, że samo jest liczbą pierwszą.
Sito Eratostenesa – metoda znajdowania liczb pierwszych
Metoda dająca odpowiedź na pytanie, czy dana liczba naturalna jest pierwsza, czy nie, nosi nazwę testu pierwszości. Wśród takich metod praktyczne zastosowanie mają testy probabilistyczne, to znaczy takie, które pozwalają określić pierwszość liczby z dostatecznie dużym prawdopodobieństwem, np.: test pierwszości Millera-Rabina, test pierwszości Solovaya-Strassena.
Rozkład !