Sito Eratostenesa
Problemem liczb pierwszych zajmowali się matematycy od bardzo dawna. Jednym z nich był matematyk grecki Eratostenes z Cyreny, żyjący w III w. p.n.e. Wymyślona przez niego metoda wyznaczania wszystkich liczb pierwszych nie większych od zadanej liczby nosi do dziś nazwę sita Eratostenesa.
Aby sprawdzić, czy liczba naturalna $n$ jest liczbą pierwszą, należy dzielić ją przez każdą taką liczbę $k \gt 1$, gdzie $k^2 \le n$. Sposób ten nie jest najbardziej efektywną metodą, ponieważ trzeba wykonać dużą liczbę czasochłonnych dzieleń, tym większą, im większą wartość ma badana liczba.
Skoro łatwiej jest mnożyć niż dzielić, Eratostenes zamiast sprawdzać podzielność kolejnych liczb naturalnych, zaproponował usuwanie ze zbioru liczb naturalnych wielokrotności kolejnych liczb, które nie zostały wcześniej usunięte.
Sprawdźmy na przykładzie. Niech $n = 100$.
Należy postępować następująco: wypisać wszystkie liczby do $100$, wykreślić wszystkie wielokrotności
liczby pierwszej $2$, w każdym następnym kroku należy wykreślić wszystkie wielokrotności najmniejszej kolejnej nie
wykreślonej liczby $p$, które są większe od $p$. Wystarczy to zrobić dla takich $p$, że $p^2 \le 100$, w naszym przypadku dla
liczb pierwszych $2, 3, 5, 7$. Wszystkie wielokrotności liczb $2, 3, 5, 7$ należy odsiać, liczby, które nie zostały wykreślone
są liczbami pierwszymi.
W XIX wieku dzięki wysiłkowi wielu badaczy opublikowano tablice zawierające wszystkie liczby pierwsze i rozkłady liczb złożonych na czynniki pierwsze aż do 10 000 000. Tablice te wyliczono za pomocą sita Eratostenesa, a przedstawił je na początku XX w. Norman Lehmer w dziele Factor Table for the First Ten Milion.