Sito Eratostenesa

O algorytmie

Sito Eratostenesa jest to algorytm wyznaczanie liczb pierwszych mniejszy, równych podanej liczbie n. Wymyślenie i zastosowanie tej metody przypisuje się Eratostenesowi z Cyreny. Zasada działania opiera sie na wiedzy, że liczbą pierwszą nie może być żadna wielokrotność dotychczas znalezionej liczby pierwszej. Najprostszym przykładem jest liczba 2. Jest to jedyna przysta liczba pierwsza, ponieważ każda prócz niej samej jest wielokrotnością 2.

Wadą sita Eratostenesa jest fakt, że chcąc wyznaczyć kolejną liczbę pierwszą musimy znać wszystkie poprzednie. Innymi słowy algorytm ten nadaje się do wyznaczania liczb pierwszych z określonego zakresu niż sprawdzania pojedynczych n. Złożoność sita Eratostenesa wynosi Θ(n·log(log(n))). Porównując z tradycyjnym algorytmem sprawdzania czy liczba jest pierwsza o złożoności Θ(√n) omawiany algorytm szybko zostaje w tyle. Jednak przy wyznaczaniu zakresu złożoność się nie zmienia, a w porównywanym algorytmie złożoność wzrasta do Θ(n√n). Tym razem role się odwracają i sito obejmuje prowadzenie.

Działanie

Przyjmijmy, że trzeba wyznaczyć wszystkie liczby pierwsze od 2 do 10. W tym celu warto stworzyć tabelkę pomocniczą, która posłuży do wykreślenia wielokrotności znalezionych liczb pierwszych.

Pierwsza liczba pierwsza to 2. Oznaczamy ją i z tabelki wykreślamy wszystkie jej wielokrotności:

Kolejny krok polega teraz na znalezieniu kolejnej nie skreślonej liczby. W tym przypadku jest to liczba 3. Teraz wystarczy wykonać to samo co w przypadku liczby 2. Podczas wykreślenia można zauważyć, że niektóre pola już są wykreślone poprzednio. Nie należy się tym przejmować - wystarczy kontynuować wykreślanie nie wykreślonych liczb.

Kolejny znaleziona liczba to 5. W tym zakresie wykreśli tylko liczbę 10 (już skreśloną przez 2), więc liczbą pierwszą będzie też z całą pewnością 7.

Przy pomocy algorytmu Eratostenesa udało się wyznaczyć wszystkie liczby pierwsze z zakresu [2, n]. Są to: {2, 3, 5, 7}.

Przygotowanie do implementacji

Podczas implementacji wykorzystanie tablic statycznych może okazać się mało optymalne - nie zawsze wiadomo ile jest liczb pierwszych w zakresie [2, n], dlatego w rozwiązaniu został użyty vector z biblioteki o tej samej nazwie, który pozwala na swobodne zarządzanie listą.

Implementacja

Funkcja eratostenes() będzie zwracać listę elementów w zmiennej typu vector dla zadanego argumentu n, który będzie wyznaczał zakres dla którego poszukiwane są liczby pierwsze.

1. vector <int> eratostenes (int n){
2.   vector <int> v;
3.   if(n >= 2) {
4.     v.push_back(2);
5.     for(int i = 3; i <= n; i += 2){
6.       eratostenes_isprime(v, i);
7.     }
8.   }
9.   return v;
10. }

(2.) Dekleracja zmiennej v typu vector, która będzie przechowywać wyznaczone jest liczby pierwsze. (3.) Wyznaczanie ma sens tylko, gdy n nie jest mniejsze od 2. (4.) Można pominąć sprawdzanie liczb parzystych dodając do listy 2, a następnie (5.) sprawdzając tylko liczby nieparzyste z zakresu [3, n]. Dla każdej liczby nieparzystej wywoływana jest funkcja pomocnicza eratostenes_isprime(), która doda liczbę i wtedy i tylko wtedy, gdy żadna liczba z wektora v nie dzieli i. (9.) Na koniec należy zwrócić wektor v.

Pomocnicza funkcja eratostenes_isprime() wygląda następująco:

1. void eratostenes_isprime (vector <int> &v, int a){
2.   for(int i = 0; i < v.size(); i++){
3.     if(a % v[i] == 0){
4.       return;
5.     }
6.   }
7.   v.push_back(a);
8. }

(2.) Dla każdego elementu z v sprawdzamy (3.) czy dzieli a. Jeśli tak to (4.) funkcja jest przerywana. Jednak jeśli nie ma elementu w v dzielącego a to (7.) dodajemy a do listy v.

Testowanie funkcji

Poniższa funkcja main() poprosi użytkownika o wprowadzenie liczby n, a następnie na ekran zostaną wypisane wszystkie liczby pierwsze z przedziału [1, n].

1. int main () {
2.   int n;
3.   cin >> n;
4.   vector <int> v = eratostenes(n);
5.   for(int i = 0; i < v.size(); i++){
6.     cout << v[i] << " ";
7.   }
8.   system("pause");
9.   return 0;
10. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Wiadomo, że sita Eratostenesa nie należy używać do sprawdzania czy konkretne n jest liczbą pierwszą. Jednak można zoptymalizować algorytm tak, aby był lepiej przystosowany do tego zadania. Złożoność czasowa powinna być niewiele gorsza od Θ(√n), a pamięciowa Θ(n).

Wskazówka: warto wykorzystać pewną cechę liczb pierwszych, która jest wykorzystywana do optymalizacji typowego algorytmu do sprawdzania czy liczba jest pierwsza.

• Kod źródłowy Zadanie 1