Sito Eratostenesa w pascalu

Algorytm rozwiązywania równania liniowego
Liczby pierwsze

program l_pierwsze;

const MAX=100000;
var skr: array[2..MAX] of boolean;
  n,i,j: integer;

begin
  write('Liczby pierwsze z zakresu od 2 do n = ');
  readln(n);
  if n>MAX then writeln('Program sprawdza zakres od 2 do maksymalnie ',MAX)
  else if n<2 then writeln('Brak liczb pierwszych w podanym zakresie')
  else begin
    for i:=2 to n do skr[i]:=false;
    i:=2;
    repeat
      if not skr[i] then begin
        j:=i*i;
        while j<=n do begin
          skr[j]:=true;
          j:=j+i;
        end;
      end;
      i:=i+1;
    until i*i>n;
    for i:=2 to n do if not skr[i] then write(i:10);
  end;
  readln;
end.

 Pierwszą linię programu możemy traktować jako ozdobnik, jednak wymagany przez składnię języka pascal. Każdy program w pascalu musi się zaczynać słowem kluczowym program poprzedzającym nazwę programu, nie wnosi nic do realizacji algorytmu.

 W trzeciej linii definiujemy stałą 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.

 Czwarta i piąta linia mają charakter pomocniczy. Wiemy, że nasz program korzysta z jednej zmiennej tablicowej o nazwie skr, przechowującej wartości logiczne typu boolean. Deklarując zmienną tablicową musimy podać w nawiasie kwadratowym początkową i końcową wartość indeksu tablicy oraz po słowie kluczowym of typ przechowywanych w tablicy elementów. Dolną wartością jest 2, górną wyznacza wartość zdefiniowanej wcześniej stałej MAX. Wiemy również, że wykorzystamy trzy zmienne przechowujące liczby całkowite, które deklarujemy w linii 5. W pascalu wszystkie zmienne muszą być zadeklarowane przed rozpoczęciem bloku kodu. Deklarując zmienną musimy podać jakiego typu dane będą w niej przechowywane.

 Siódma linia zawierająca słowo kluczowe begin odpowiada blokowi startowemu (1) naszego algorytmu.

 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 pascalu 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 pomiędzy słowami kluczowymi begin ... end (zwanymi często nawiasami logicznymi). W linii 12 po słowie else umieściliśmy begin rozpoczynające ciąg instrukcji, które mają zostać wykonane gdy do zmiennej n wprowadziliśmy prawidłową wartość. Ten ciąg instrukcji kończy dopiero end z 26 linii programu.

 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 13 programu. Dolną granicę zmiennej i (zmiennej sterującej pętli for) ustaliliśmy na 2 (for i:=2), górną granicę na n (to n). Po słowie kluczowym do 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.

 W linii 14 realizujemy punkt (8) algorytmu, przypisujemy zmiennej pomocniczej i wartość 2.

 Punkty (9) do (14) możemy odczytać: dla kolejnych wartości i poczynając od 2 skreśl wszystkie wielokrotności i. Skreślaj dopóki i nie spełni warunku: i*i>n. W pascalu instrukcją realizującą schemat "wykonuj dopóki nie zostanie spełniony warunek" jest pętla:

repeat instrukcje until warunek.

 Wykonanie ciągu instrukcji zawartych pomiędzy słowami kluczowymi repeat oraz until jest powtarzane tak długo jak długo nie jest spełniony warunek po słowie until. Spełnienie tego warunku jest sprawdzane po każdorazowym wykonaniu całego ciągu instrukcji, instrukcje zostaną wykonane co najmniej jeden raz (przed pierwszym sprawdzeniem warunku). Jeśli warunek nie jest spełniony cały ciąg instrukcji jest wykonywany ponownie i znów sprawdzany jest warunek - i tak wkoło. Gdy warunek zostanie wreszcie 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 repeat until.

 W linii 15 słowem kluczowym repeat rozpoczynamy naszą pętlę repeat until. W linii 16 sprawdzamy czy liczba i nie została już wcześniej skreślona (9). Warunek if not skr[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 17 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 pascalu instrukcją realizującą schemat "dopóki warunek jest spełniony wykonuj instrukcję" jest pętla:

while warunek do instrukcja

Dopóki warunek zapisany po słowie kluczowym while jest spełniony wykonuj instrukcję umieszczoną po słowie kluczowym do. Należy zauważyć, że po słowie kluczowym do znajduje się dokładnie jedna instrukcja. Jeśli potrzebujemy umieścić w tym miejscu więcej instrukcji musimy je zapisać w nawiasach logicznych begin end

 W linii 18 rozpoczynamy pętlę while, która będzie wykonywana dla wszystkich wartości j mniejszych od n. W liniach 19 - 20 znajdują się pomiędzy słowami kluczowymi begin end instrukcje wykonywane w pętli. W linii 19 elementowi o numerze j tablicy skr przypisujemy wartość true (skreślamy j), a następnie w linii 20 zwiększamy wartość j do następnej wielokrotności liczby i - punkt (12) algorytmu. W linii 21 słowo kluczowe end zamyka nawias logiczny begin end otwarty w linii 18.

 Słowo kluczowe end w linii 22 zamyka z kolei nawias logiczny begin end rozpoczęty w linii 16 po instrukcji if sprawdzającej czy liczba nie była już wcześniej skreślona.

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

 Linia 24 kończy pętlę repeat until, w której wykreślamy wszystkie wielokrotności kolejnych liczb. Zawarty jest w niej warunek zakończenia pętli x*x>n. Gdy warunek 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 25. Gay warunek nie jest spełniony wracamy na początek pętli do linii 16.

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

 Słowo kluczowe end z linii 26 kończy instrukcję warunkową z linii 11, jej część zawartą po słowie kluczowym else z linii 12.

 Instrukcja readln w linii 27 nie ma żadnego związku z wykonaniem algorytmu znajdowania liczb pierwszych. Służy ona zatrzymaniu programu do czasu naciśnięcia klawisza enter, co zapobiega natychmiastowemu zamknięciu okienka z programem.

 Instrukcja end. z linii 38 kończy działanie programu (blok końca algorytmu (20)).

loadposition Spis-mod_AP}