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.
algorytm >>Poniżej możesz wygenerować liczy pierwsze, mniejsze do zadeklarowanej górnej granicy (1 < n < 1 000), za pomocą algorytmu wykorzystującego metodę sita Eratostenesa.