Sito Eratostenesa
Problemem liczb pierwszych zajmowali się matematycy od bardzo dawna. Jednym z pierwszych był matematyk grecki Eratostenes z Cyreny, żyjący w III wieku przed Chrystusem. 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, gdzie k2 ≤ n. Sposób ten nie jest najefektywniejszą metodą wyszukiwania liczb pierwszych, gdyż trzeba wykonać dużą ilość 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 to na przykładzie dla n = 100.
Należy postępować następująco: wypisać wszystkie liczby do 100; wykreślić wszystkie wielokrotności
liczby 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 p2 ≤ 100.
Tak więc wszystkie wielokrotności liczb zostały odsiane. 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". Papier na którym Lehmer zapisywał swoje obliczenie, spoczywał na bardzo długim stole.
