Eratosthenes sieve in Pascal


prime<<algorithm

program sieve;

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

begin
  write('n = ');
  readln(n);
  if n>MAX then writeln('n must be betwen 2 to ',MAX)
  else if n<2 then writeln('Bad n')
  else begin
    for i:=2 to n do del[i]:=false;
    i:=2;
    repeat
      if not del[i] then begin
        j:=i*i;
        while j<=n do begin
          del[j]:=true;
          j:=j+i;
        end;
      end;
      i:=i+1;
    until i*i>n;
    for i:=2 to n do if not del[i] then write(i:10);
  end;
  readln;
end.

The first line of the program can be treated as an ornament, but required by pascal syntax. Every program in the pascal must start with the keyword program preceding the program name, it does not contribute anything to the implementation of the algorithm.

 In the third line we define the MAX constant, defining the maximum upper boundary of the range in which we will look for prime numbers. The lower limit is always equal to 2. The maximum amount that can be set to MAX depends on the compiler we use and the amount of memory available for the memory program.

 Fourth and fifth lines are auxiliary. We know that our program uses one array variable named del, which stores boolean values. Declaring an array variable we must specify in square brackets the starting and ending values ​​of the array index and after the keyword of the type stored in the element array. The lower value is 2, the upper determines the value of the predefined MAX constant. We also know that we will use three variables that store integers that we declare on line 5. In the pascal, all variables must be declared before the code block. Declaring a variable we have to specify what type of data will be stored in it.

 The seventh line containing the begin keyword corresponds to the startup block (1) of our algorithm.

 Lines 8 and 9 perform an input/output operation (2) in which input data is input - the upper limit of the range of the prime numbers.

 In line 10 we check whether we have enough space in the table to make the remainder of the algorithm. If n> MAX means that the given number exceeds the acceptable retention range of the deletion information stored in the short table. In that case, we print the corresponding message and continue to execute the algorithm. Otherwise, if the value of n is not too large, we check line 11 or n is not too small (can not be less than 2) - point (3) of the algorithm. In this case, we also issue the error message (4) and we will not continue to execute the algorithm.

 On the line 12 again the keyword else appears. This else applies to the second if statement (from line 11). In the pascale after the else keyword, there may be exactly one instruction that is executed when the condition of the if statement is not fulfilled. When we want to write more instructions here, we have to write them between the begin end (often called the logical brackets). In line 12, after the word else, we put begin, which begins the set of instructions to be executed when we enter a valid value into variable n. This instructions set ends only the end of the 26 program lines.

 Points (5) to (7) of our algorithm can be read: starting with element 2, ending with element n, assign the next element of the array del false. The implementation of these three points of the algorithm we entered in line 13 of the program. The lower limit of the variable (and the for loop control variable) was set to 2 (for i: = 2), the upper limit for n (to n). After the keyword do, there is a statement executed in turn for each value i: del[i]: = false. In this way, we have initialized all the array elements used by the algorithm del to be false. It is worth noting here that if n <MAX we do not use in the program of the entire table del, but only its first n elements and only those elements initialize, the rest do not matter to us.

 In line 14, we execute point (8) of the algorithm, assign an auxiliary variable i value 2.

 Points (9) to (14) can be read: for subsequent values ​​and beginning with 2, delete all multiple i. Subtract until and do not satisfy the condition: i*i> n. In the tutorial, executing the "execute until the condition is true" statement is a loop:

repeat instructions until condition.

 The execution of a set of statements between the repeat and until keywords is repeated as long as the condition until word is not met. The fulfillment of this condition is checked every time the whole string of instructions is executed, the instructions will be executed at least once (before the first condition check). If the condition is not fulfilled the entire instruction string is executed again and the condition is checked again - and so on. When the condition is finally fulfilled, the program does not return to the start of the loop, but goes on to execute the remainder of the program that is behind the repeat until loop.

 In line 15 the repeat keyword starts our loop repeat until. On line 16 we check the number and have not already been deleted (9). The if not del[i] condition is satisfied when del[i] is false, which means that the number has not been deleted (it is a prime number) and we have to delete all its multiple.

The first multiple that must be subtracted is i2 (in line 17 we assign j:=i*i) (see justification for the algorithm description) - point (10) of the algorithm. Points (11) - (12) can be read: as long as j<=n subtract j and increase j by i (assign to j the multiple of i). In the statement, the instruction that executes the schema "as long as the condition is true execute the statement" is a loop:

while condition to statement

As long as the condition written after the while keyword is fulfilled, execute the statement placed after the keyword to. It should be noted that after the keyword to have exactly one statement. If we need to place more instructions here, we need to write them in the begin end of the logical brackets.

 While in line 18, we start the while loop, which will be executed for all j values ​​less than n. In lines 19-20 there are between the begin end of the instructions in the loop. In line 19, the element with the number j of the array del is set to true, and then in line 20 we increase j to the next multiple of the number i - point (12) of the algorithm. In line 21, the end keyword closes the parenthesized begin end in line 18.

 The end keyword on line 22 closes in turn the begin end bracket starting at line 16 after the if statement checking whether the number has already been deleted.

 In line 23 we execute (13) the algorithm point, we increment i by 1 we are preparing this way to subtract the multiple of the next number.

 Line 24 ends the repeat until loop, in which we plot all multiples of consecutive numbers. It contains the termination condition of the loop x*x>n. When the condition is fulfilled (there is nothing left to draw), the program terminates the loop and proceeds to the statement contained in line 25. The gay condition is not fulfilled, we return to the beginning of the loop to line 16.

 In line 25 we write in the for loop all numbers in the range 2 to n, which were not deleted (not del[i]) - the prime numbers.

 The end keyword from line 26 completes conditional line 11, part of which follows the else line from line 12.

 The readln instruction on line 27 has no relation to the execution of the prime numbers algorithm. It is used to stop the program until you press the enter key, preventing immediate closure of the program window.

 end. instruction in line 38 ends the program (end of algorithm - block (20)).