Przykład optymalizacji sita Eratostenesa w języku C++

Algorytm sita Eratostenesa możemy optymalizować. Przeanalizujmy jeden z przykładów takiej optymalizacji.

Zanim przystąpimy do pisania kodu, trzeba zauważyć, że jedyną parzystą liczbą pierwszą jest 2 - każda kolejna liczba parzysta: 4, 6, 8, ... jest złożona.

Utwórzmy tablicę $tab$, składającą się z 26 komórek, której elementy będą przechowywać kolejne liczby nieparzyste, zaczynając od liczby 3. W języku C++ tablice indeksujemy od 0 – na potrzeby omawianego algorytmu komórkę kryjącą się pod tym indeksem wypełnimy wartością 0; pomoże nam to w lepszym zrozumieniu algorytmu. Tablica $tab$ będzie więc składała się z następujących elementów: pod indeksem 1 będzie kryła się wartość 3. Możemy przyjąć, że: $tab[2] = 5$, $tab[3] = 7$ ... $tab[25] = 51$.

RVVLMlbb8rr8H

Tabelka przedstawia 2 rzędy liczb, rząd oznaczony jako i, to liczby od 0 do 25. Rząd oznaczony jako k, to liczby nieparzyste, pierwszą ustawioną liczbą jest 0.

Zauważmy, że dzięki wypełnieniu tablicy danymi od indeksu 1 możemy wprowadzić korelacje między numerem indeksu, a wartością, jaką ten indeks przechowuje.

Komórka $k$ o indeksie $i$ będzie przechowywać liczbę o wartości:

$k = 2 * i + 1$

Np. komórka o indeksie 9 będzie przechowywać wartość $2*9+1=19$, z kolei komórka o indeksie 15: $2 * 15 + 1 = 31$.

Wyprowadzenie wzoru przedstawionego powyżej pozwala nam w łatwy sposób obliczyć indeks komórki, w której została zapisana wartość $k$.

$i = \frac{k-1}{2}$

Ponownie rozpatrzmy kilka przykładów. Liczba 59 będzie przechowywana pod indeksem 29, ponieważ $\frac{59-1}{2} = 29$; z kolei liczba 49 będzie przechowywana pod indeksem 24.

Na potrzeby niniejszego algorytmu wprowadźmy dwie zmienne indeksowane:

• $a_n$ – indeks kwadratu liczby, której wielokrotność usuwamy z tablicy $tab$,

• $d_n$ – odstęp (liczba komórek w tablicy $tab$) między kolejnymi wielokrotnościami, które będziemy wykreślać.

Algorytm zaprezentowany w poprzedniej sekcji tłumaczył, dlaczego pierwszą „wykreślaną” wielokrotnością jest kwadrat przetwarzanej liczby. Tablica $tab$ pod indeksem 1 przechowuje liczbę 3 – jej kwadratem jest liczba 9, kryjąca się pod indeksem $a_0 = 4$. Zauważmy, że kolejne wielokrotności liczbywielokrotność liczbywielokrotności liczby 3 znajdują się w odległości $d_0 = 3$ – te liczby nie są liczbami pierwszymi; wykreślamy je.

R12A0kIMqMegG

Tabelka przedstawia 2 rzędy liczb, rząd oznaczony jako i, to liczby od 0 do 25. Rząd oznaczony jako k, to liczby nieparzyste, pierwszą ustawioną liczbą jest 0. Oznaczono kolorami różne kolumny. Niebieskim kolumnę z liczbami 1 oraz 3. Czerwonym kolumny 4, 9 7, 15 10, 21 13, 27 16, 33 19, 39 22, 45 25, 51. Oznaczono jako a 0 kolumnę 4, 9. Z tej kolumny poprowadzoną strzałkę z oznaczeniem d 0 równa się 3.

Kolejną niewykreśloną liczbą jest 5. Jej kwadrat – 25 kryje się pod indeksem $a_1 = 12$. Zauważmy, że wartość $a_1$ możemy przedstawić również jako $a_1= a_0 + 8 = 4 + 8 = 12$ (dokładne omówienie wzoru nastąpi poniżej). Dystans między kolejnymi wielokrotnościami liczby 5 wynosi $d_1 = 5$ i możemy go przedstawić jako $d_1 = d_0 + 2 = 3 + 2 = 5$. Ponownie wykreślamy wielokrotności.

R14Eo2iPARyKH

Tabelka przedstawia 2 rzędy liczb, rząd oznaczony jako i, to liczby od 0 do 25. Rząd oznaczony jako k, to liczby nieparzyste, pierwszą ustawioną liczbą jest 0. Oznaczono kolorami różne kolumny. Niebieskim kolumnę z liczbami 2 , 5. Czerwonym kolorem oznaczono kolumny 12, 25 17, 25 22, 45. Przekreślono kolumny 4, 9 7, 15 10, 21 13, 27 16, 33 19, 39 22, 45 25, 51. Oznaczono jako a 1 kolumnę 12, 25. Z tej kolumny poprowadzoną strzałkę z oznaczeniem d 1 równa się 5.

Proces powtarzamy dla liczby 7. Jej kwadrat – 49 został zapisany pod indeksem $a_2 = 24$ ($a_2 = a_1 + 12 = a_0 + 8 + 12 = 4 + 8 + 12 = 24$). Dystans między jej kolejnymi wielokrotnościami wynosi $d_2 = 7$ ($d_2 = d_1 + 2 = d_0 + 2 + 2 = 3 + 2 + 2 = 7$).

R10eJf4PRoMGh

Tabelka przedstawia 2 rzędy liczb, rząd oznaczony jako i, to liczby od 0 do 25. Rząd oznaczony jako k, to liczby nieparzyste, pierwszą ustawioną liczbą jest 0. Oznaczono kolorami różne kolumny. Niebieskim kolumnę z liczbami 3, 7. Czerwonym kolorem oznaczono kolumny 24, 49 31, 63. Przekreślono kolumny 4, 9 7, 15 10, 21 13, 27 16, 33 19, 39 22, 45 25, 51 12, 25 17, 25 22, 45. Oznaczono jako a 2 kolumnę 24, 49. Z tej kolumny poprowadzoną strzałkę z oznaczeniem d 2 równa się 7.

Następna liczba (9) została wykreślona już wcześniej. Aby lepiej zrozumieć algorytm,  omówmy i ją. Wskazujemy indeks komórki, w której umieszczono kwadrat liczby 9, czyli 81: $a_3 = 40$ ($a_3 = a_2 + 16 = 24 + 16 = 40$). Odległość między wielokrotnościami wynosi $d_3 = 9$ ($d_3 = d_2 + 2 = 7 + 2 = 9$). Zauważmy, że liczba 81 (kwadrat liczby 9) znajduje się poza zakresem tablicy $tab$. Jest to moment, w którym przerywamy algorytm.

RyNGn0CT7iUro

Tabelka przedstawia 2 rzędy liczb, rząd oznaczony jako i, to liczby od 0 do 25. Rząd oznaczony jako k, to liczby nieparzyste, pierwszą ustawioną liczbą jest 0. Oznaczono kolorami różne kolumny. Niebieskim kolumnę z liczbami 4, 9. Czerwonym kolorem oznaczono kolumny 40, 81 49, 99. Przekreślono kolumny 4, 9 7, 15 10, 21 13, 27 16, 33 19, 39 22, 45 25, 51 12, 25 17, 25 22, 45. Oznaczono jako a 3 kolumnę 40, 81. Z tej kolumny poprowadzoną strzałkę z oznaczeniem d 3 równa się 9.

Na podstawie przedstawionych rozważań możemy zbudować tabelę:

Zauważmy, że kolejne $d$ powstaje poprzez dodanie do poprzedniej wartości liczby 2. Podobną zależność jesteśmy w stanie wyprowadzić dla $a_i$ – do poprzedniej wartości dodajemy $2 * (d_{i} - 1)$.

W ten sposób dotarliśmy do momentu, w którym możemy wyprowadzić następujący wzór rekurencyjny:

• $d_0 = 3$,

• $a_0 = 4$,

• dla każdego $i$ > $0$:

  • $d_i = d_{i-1} + 2$

  • $a_i = a_{i-1} + 2 * (d_i - 1)$.

Implementacja algorytmu

Implementacje algorytmu rozpocznijmy od zadeklarowania funkcji main, wczytania biblioteki iostream oraz poinformowania kompilatora o wykorzystaniu typów pochodzących z biblioteki standardowej.

 #include <iostream>
 
 using namespace std;


 int main() {
 
 }
   

Tworzymy zmienną n, która będzie przechowywać rozmiar generowanego sita. Zapisujemy w niej liczbę naturalną dodatnią pobraną od użytkownika.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
 }
   

Przedstawiony algorytm nie wymaga do swojego działania tablicy o długości n. Już na wstępie do omawiania algorytmu założyliśmy wykreślenie wszystkich liczb parzystych większych od 2 – potrzebujemy tylko połowy komórek, które użylibyśmy w przypadku niezoptymalizowanego algorytmu sita Eratostenesa.

Sprawdzamy, czy wprowadzona przez użytkownika liczba n jest nieparzysta. Jeżeli badany warunek jest prawdziwy, wówczas zwiększamy wartość n o 1.

Tworzymy zmienną pomocniczą polowa, którą wykorzystamy do tworzenia tablicy, a także jako warunek wykonania kolejnych pętli.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
    
    if(n % 2 == 1){
        n += 1;
    }
    
    int polowa = n / 2;
 }
   

Następnie tworzymy tablicę wartości logicznych tab o długości polowa. Wypełniamy ją wartościami true. Dlaczego w komórkach tablicy przechowujemy wartości logiczne, skoro podczas omawiania algorytmu przez cały czas pokazywaliśmy liczby naturalne?

Zauważmy, że dzięki wyprowadzeniu korelacji między $i$ – indeksem komórki tablicy oraz $k$ – wartością przechowywaną w komórce, nie musimy zapisywać informacji o liczbie kryjącej się pod indeksem. Podobnie jak w przypadku niezoptymalizowanego algorytmu sita Eratostenesa, jeżeli komórka kryjąca się pod indeksem i przechowuje wartość false, oznacza to wykreślenie liczby k. Co więcej, sam algorytm opiera się na badaniu odległości między kolejnymi indeksami zapisanymi w tablicy – same liczby są wyłącznie dodatkową reprezentacją.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
    
    if(n % 2 == 1){
        n += 1;
    }
    
    int polowa = n / 2;
    bool tab[polowa];

    for(int x = 0; x < polowa; x++){
        tab[x] = true;
    }
 }

Dodajemy kolejne zmienne:

• i – będzie wskazywać akualnie przetwarzany indeks tablicy tab,

• d – będzie wskazywać odległość między kolejnymi wykreślanymi indeksami,

• a – będzie przechowywać pierwszą wielokrotność liczby kryjącej się pod indeksem i.

Zmienną d inicjalizujemy wartością 3, z kolei zmienną a wartością 4. Są to wartości początkowe wcześniej przedstawionego wzoru rekurencyjnego.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
    
    if(n % 2 == 1){
        n += 1;
    }
    
    int polowa = n / 2;
    bool tab[polowa];

    for(int x = 0; x < polowa; x++){
        tab[x] = true;
    }
    
    int i = 1;
    int d = 3;
    int a = 4;
 }

Dodajemy pierwszą pętlę – while. Będzie się wykonywać, dopóki nie przekroczymy badanego zakresu. W jej wnętrzu sprawdzamy, czy komórka kryjąca się pod indeksem i przechowuje wartość true – oznacza to, że badana liczba nie została wykreślona wcześniej, czyli jest pierwsza.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
    
    if(n % 2 == 1){
        n += 1;
    }
    
    int polowa = n / 2;
    bool tab[polowa];

    for(int x = 0; x < polowa; x++){
        tab[x] = true;
    }
    
    int i = 1;
    int d = 3;
    int a = 4;
    
    while(a < polowa){
        if(tab[i] == true){
            
        }
    }
 }

Jeżeli liczba kryjąca się pod indeksem i jest pierwsza, czyli przedstawiony warunek jest prawdziwy, musimy wykreślić jej wielokrotności. Tworzymy zmienną pomocniczą z, do której przypisujemy indeks pierwszej wielokrotności liczby kryjącej się pod indeksem i. Następnie w zagnieżdżonej pętli while ustawiamy wartość false kolejnym indeksom oddalonym o d.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
    
    if(n % 2 == 1){
        n += 1;
    }
    
    int polowa = n / 2;
    bool tab[polowa];

    for(int x = 0; x < polowa; x++){
        tab[x] = true;
    }
    
    int i = 1;
    int d = 3;
    int a = 4;
    
    while(a < polowa){
        if(tab[i] == true){
            int z = a;
            while(z < polowa){
                tab[z] = false;
                z += d;
            }
        }
    }
 }

Poza instrukcją warunkową zwiększamy wartość iteratora i. Zgodnie z przedstawionym wcześniej wzorem wyznaczamy nowe wartości zmiennych d oraz a.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
    
    if(n % 2 == 1){
        n += 1;
    }
    
    int polowa = n / 2;
    bool tab[polowa];

    for(int x = 0; x < polowa; x++){
        tab[x] = true;
    }
    
    int i = 1;
    int d = 3;
    int a = 4;
    
    while(a < polowa){
        if(tab[i] == true){
            int z = a;
            while(z < polowa){
                tab[z] = false;
                z += d;
            }
        }
        i++;
        d += 2;
        a = a + 2 * (d - 1);
    }
 }

Implementacje algorytmu kończymy, wypisując wszystkie niewykreślone liczby pierwsze, zaczynając od liczby 2. Wewnątrz pętli for sprawdzamy, czy wartość zapisana pod indeksem i przechowuje wartość true. Jeżeli warunek jest prawdziwy, wówczas liczymy wartość zmiennej k zgodnie z wcześniej przedstawionym wzorem i drukujemy na standardowym wyjściu.

 #include <iostream>
 
 using namespace std;


 int main() {
 	int n = 0;
 	cin >> n;
    
    if(n % 2 == 1){
        n += 1;
    }
    
    int polowa = n / 2;
    bool tab[polowa];

    for(int x = 0; x < polowa; x++){
        tab[x] = true;
    }
    
    int i = 1;
    int d = 3;
    int a = 4;
    
    while(a < polowa){
        if(tab[i] == true){
            int z = a;
            while(z < polowa){
                tab[z] = false;
                z += d;
            }
        }
        i++;
        d += 2;
        a = a + 2 * (d - 1);
    }
    
    cout << 2 << " ";
    for(int i = 1; i < polowa; i++){
        if(tab[i] == true){
            int k = 2 * i + 1;
            cout << k << " ";
        }
    }
 }

Przykład działania  kodu dla $n = 100$.

Słownik