Sito Eratostenesa w C++

 

Algorytm rozwiązywania równania liniowego

Sito Eratostenesa

#include <iostream>
#include <iomanip>
using namespace std;
const int MAX = 100000;

int main(void) {
    int n;
    cout << "n = ";
    cin >> n;
    if(n > MAX) cout << "Program sprawdza zakres od 2 do maksymalnie " << MAX;
    else if(n < 2) cout << "Brak liczb pierwszych w podanym zakresie" << endl;
    else{
      bool skr[MAX+1];
      for(int i = 2;i <= n;i++) skr[i] = false;
      int i=2, j;
      do{
        if(!skr[i]){
          j=i*i;
          while(j<=n){
            skr[j]=true;
            j+=i;
          };
        };
        i++;
      }while(i*i<=n);
      for(int i=2;i<=n;i++) if(!skr[i]) cout<<setw(8)<<i;
    };
    cout<<endl;
    char c;
    cin >> c;
}

 W pierwszej linii programu dołączamy plik nagłówkowy biblioteki iostream (strumieni wejścia-wyjścia). Jest to niezbędne, gdyż w dalszej części programu będziemy chcieli mieć możliwość pisania na ekranie (cout) i wczytywania danych wejściowych z klawiatury (cin). W drugiej linii dołączamy plik nagłówkowy biblioteki iomanip, którą wykorzystamy do formatowania danych wyjściowych. W trzeciej linii informujemy kompilator, że będziemy używać w programie nazw zdefiniowanych w przestrzeni nazw std (będą to: cin, cout, endl, setw), gdybyśmy tego nie uczynili konieczne byłoby używanie dłuższego zapisu nazw kwalifikowanych (std::cin, std::cout, std::endl, std::setw). W następnej linii definiujemy stałą całkowitą MAX, określającą maksymalną górną granicę przedziału, w którym będziemy poszukiwali liczb pierwszych. Dolna granica jest zawsze równa 2. Ile maksymalnie może wynosić wartość stałej MAX zależy od kompilatora, którego używamy i ilości dostępnej dla programu pamięci operacyjnej.

 W języku C++ program rozpoczyna się od wykonania funkcji main. W naszym przykładzie jest to jedyna funkcja programu. Linia 6 zawiera początek definicji funkcji main, jest to początek realizacji naszego algorytmu (blok START (1)). W kolejnej linii deklarujemy zmienną całkowitą n, którą za chwilę będziemy używali. W C++ zmienne można deklarować w dowolnym miejscu przed ich użyciem, dlatego nie deklarujemy tutaj od razu zmiennych i, j, skr, które być może wcale nie będą nam potrzebne.

  Linie 8 i 9 realizują operację wejścia/wyjścia (2), w której pobierane są dane wejściowe - górna granica zakresu poszukiwania liczb pierwszych.

 W linii 10 sprawdzamy, czy wystarczy nam miejsca w tablicy skr do wykonania dalszej części algorytmu. Jeśli n>MAX to znaczy, że podana liczba przekracza dopuszczalny zakres przechowywania informacji o skreśleniu liczb, przechowywanej w tablicy skr. W takim przypadku wypisujemy odpowiedni komunikat i nie kontynuujemy wykonywania algorytmu. W przeciwnym przypadku (słowo kluczowe else), czyli gdy wartość n nie jest za duża sprawdzamy w linii 11 czy n nie jest za małe (nie może być mniejsze od 2) - punkt (3) algorytmu. W takiej sytuacji również wypisujemy komunikat o błędnej wartości (4) i nie kontynuujemy wykonywania algorytmu.

 W linii 12 ponownie pojawia się słowo kluczowe else. To else odnosi się do drugiej instrukcji if (z linii 11). W języku C++po słowie kluczowym else może znaleźć się dokładnie jedna instrukcja, która jest wykonywana wtedy, gdy warunek z instrukcji if nie został spełniony. Gdy chcemy zapisać w tym miejscu więcej instrukcji musimy zapisać je w nawiasach klamrowych {...} (zwanych często nawiasami logicznymi). W linii 12 po słowie else umieściliśmy nawias otwierający { rozpoczynający ciąg instrukcji, które mają zostać wykonane gdy do zmiennej n wprowadziliśmy prawidłową wartość. Ten ciąg instrukcji kończy dopiero nawias zamykający end z 27 linii programu.

 W dalszej części programu będziemy wykorzystywali tablicę skr przechowującą wartości logiczne typu boolean, przed użyciem deklarujemy ją w linii 13. Deklarując zmienną tablicową musimy podać w nawiasie kwadratowym umieszczonym po nazwie zmiennej liczbę elementów tablicy. W C++ numeracja elementów tablicy zawsze rozpoczyna się od 0. Jeśli chcemy by numer ostatniego elementu wynosił MAX musimy zadeklarować tablicę posiadającą MAX+1 elementów.

 Punkty (5) do (7) naszego algorytmu możemy przeczytać: poczynając od elementu o numerze 2 kończąc na elemencie o numerze n przypisz kolejnym elementom tablicy skr wartość logiczną false. Realizację tych trzech punktów algorytmu zawarliśmy w linii 14 programu. Dolną granicę zmiennej i (zmiennej sterującej pętli for) ustaliliśmy na 2 (for(int i=2... - deklarujemy i inicjujemy zmienną i, sterującą przebiegiem naszej pętli; zadeklarowana w tym miejscu zmienna i istnieje tylko w obrębie pętli), górną granicę na n (...,i<=n...). Po części organizacyjnej pętli występuje instrukcja wykonywana po kolei dla każdej wartości i: skr[i]:=false. W ten sposób zainicjowaliśmy wszystkie wykorzystywane przez algorytm elementy tablicy skr wartością logiczną false. Warto zauważyć w tym miejscu, że jeżeli n<MAX nie wykorzystujemy w programie całej tablicy skr, lecz tylko jej n pierwszych elementów i tylko te elementy inicjujemy, pozostałe nie mają dla nas żadnego znaczenia. Niewykorzystane pozostają również dwa pierwsze elementy tablicy (skr[0] i skr[1]).

 W linii 15 deklarujemy dwie zmienne pomocnicze: i oraz j. Jednocześnie zgodnie z punktem (8) algorytmu, przypisujemy zmiennej pomocniczej i wartość 2. Utworzona w tym miejscu zmienna i nie ma nic wspólnego ze zmienną o tej samej nazwie użytą do sterowania pętlą w linii 14. Tamta zmienna została zadeklarowana wewnątrz pętli for i istniała tylko wewnątrz tej pętli, po zakończeniu wykonywania instrukcji for została "zapomniana", zwolniona.

 Punkty (9) do (14) algorytmu możemy odczytać: dla kolejnych wartości zmiennej i poczynając od 2 skreśl wszystkie wielokrotności i. Skreślaj dopóki i nie spełni warunku: i*i>n, lub inaczej skreślaj tak długo dopóki i*i<=n. W C++ instrukcją realizującą schemat "wykonuj dopóki jest spełniony warunek" jest pętla:

do instrukcja while (warunek)

 Wykonanie instrukcji zawartej pomiędzy słowami kluczowymi do oraz while jest powtarzane tak długo jak długo jest spełniony warunek po słowie while. Spełnienie tego warunku jest sprawdzane po każdorazowym wykonaniu instrukcji, instrukcja zostanie wykonana co najmniej jeden raz (przed pierwszym sprawdzeniem warunku). Gdy warunek nie zostanie spełniony program nie wraca na na początek pętli lecz przechodzi do wykonywania dalszej części programu znajdującej się za warunkiem pętli do while. Jeśli mamy do wykonania w pętli więcej instrukcji umieszczamy je w nawiasach klamrowych.

 W linii 16 słowem kluczowym do rozpoczynamy naszą pętlę do while i otwieramy nawias klamrowy, w którym umieścimy instrukcje wykonywane w pętli. W linii 17 sprawdzamy czy liczba i nie została już wcześniej skreślona (9). Warunek if !kr[i] jest spełniony, gdy skr[i] zawiera wartość false, co oznacza, że liczba i nie została do tej pory skreślona (jest liczbą pierwszą) i musimy skreślić wszystkie jej wielokrotności. Pierwsza wielokrotność, która musi zostać skreślona ma wartość i2 (w linii 18 przypisujemy j:=i*i) (zobacz uzasadnienie przy opisie algorytmu) - punkt (10) algorytmu. Punkty (11) - (12) algorytmu możemy odczytać: dopóki j<=n skreśl liczbę j a następnie zwiększ wartość j o i (przypisz do j następną wielokrotność liczby i). W C++ instrukcją realizującą schemat "dopóki warunek jest spełniony wykonuj instrukcję" jest pętla:

while (warunek) instrukcja

 Dopóki warunek zapisany po słowie kluczowym while jest spełniony wykonuj instrukcję. Tradycyjnie jeśli potrzebujemy umieścić w tym miejscu więcej instrukcji musimy je zapisać w nawiasach logicznych {}

 W linii 19 rozpoczynamy pętlę while, która będzie wykonywana dla wszystkich wartości j mniejszych od n. W liniach 20 - 21 znajdują się w nawiasach { } instrukcje wykonywane w pętli. W linii 20 elementowi o numerze j tablicy skr przypisujemy wartość true (skreślamy j), a następnie w linii 21 zwiększamy wartość j do następnej wielokrotności liczby i - punkt (12) algorytmu. W linii 22 zamykamy nawias klamrowy z linii 19.

 W linii 23 zamykamy nawias klamrowy rozpoczęty w linii 17 po instrukcji if sprawdzającej czy liczba nie była już wcześniej skreślona.

 W linii 24 realizujemy (13) punkt algorytmu, zwiększamy i o 1 przygotowując się w ten sposób do skreślania wielokrotności kolejnej liczby.

 Linia 25 kończy pętlę do while, w której wykreślamy wszystkie wielokrotności kolejnych liczb. Zawarty jest w niej warunek kontynuowania pętli x*x<=n. Gdy warunek nie jest spełniony (nie pozostało już nic do wykreślenia) program kończy wykonywanie pętli i przechodzimy dalej do instrukcji zawartej w linii 26. Gdy warunek jest spełniony wracamy na początek pętli do linii 17.

 W linii 26 wypisujemy w pętli for wszystkie liczby z zakresu od 2 do n, które nie zostały zostały wykreślone (!skr[i]) - liczby pierwsze.

 Nawias klamrowy } z linii 27 kończy instrukcję warunkową z linii 11, jej część zawartą po słowie kluczowym else z linii 12.

 Instrukcje w liniach 28 - 30 nie mają żadnego związku z wykonaniem algorytmu dzielenia. Służą do zatrzymaniu programu do czasu wprowadzenia dowolnego znaku i naciśnięcia klawisza enter, co zapobiega natychmiastowemu zamknięciu okienka z programem.

 Nawias klamrowy } z linii 31 kończy funkcję main i zarazem działanie całego programu (blok końca algorytmu (20)).