|
|
The first line of the program can be treated as purely ornamental, though it is required by Pascal syntax. Every Pascal program must begin with the keyword program followed by the program's name; it adds nothing to the algorithm's execution.
Variable and Constant Declarations
In Line 3, we define the constant MAX, which specifies the maximum upper limit of the interval in which we will search for prime numbers. The lower limit is always 2. The maximum value of the MAX constant depends on the compiler used and the amount of operating memory available to the program.
Lines 4 and 5 are for auxiliary definitions. We know that our program uses one array variable named del, which stores Boolean values. When declaring an array, we must provide the starting and ending index values in square brackets and, after the keyword of, the type of elements stored. The lower index value is 2, and the upper index value is determined by the previously defined constant MAX. We also know that we will use three integer variables, which we declare in Line 5. In Pascal, all variables must be declared before the start of the code block. When declaring a variable, we must specify the type of data it will store.
Program Flow and Input Validation
Line 7, containing the keyword begin, corresponds to the starting block (1) of our algorithm.
Lines 8 and 9 implement the input/output operation (2), where the input data—the upper limit of the prime search range—is obtained.
In Line 10, we check if there is enough space in the del array to execute the rest of the algorithm. If n>MAX, the entered number exceeds the allowed range for storing deletion information in the del array. In this case, we output the appropriate message and do not continue executing the algorithm. In the opposite case (the keyword else), meaning n is not too large, we check in Line 11 if n is not too small (it cannot be less than 2) — point (3) of the algorithm. In this situation, we also output an error message (4) and do not continue executing the algorithm.
In Line 12, the keyword else appears again. This else refers to the second if instruction (from Line 11). In Pascal, exactly one statement can follow the keyword else, and it is executed when the condition in the if instruction is not met. If we need to place more than one instruction here, we must enclose them between the keywords begin ... end (often called logical brackets). In Line 12, after else, we placed begin, starting a sequence of instructions to be executed when a valid value was entered for the variable n. This sequence of instructions is terminated only by the end in Line 26 of the program.
Array Initialization and Main Sieving Loop
Points (5) through (7) of our algorithm can be read as: starting from element number 2 and ending with element number n, assign the logical value false to successive elements of the del array. The implementation of these three algorithm points is contained in Line 13 of the program, using a for loop: for i:=2 to n do del[i]:=false. In this way, we initialized all elements of the del array used by the algorithm. Note that if n<MAX, we are only initializing the first n elements; the rest are irrelevant.
In Line 14, we implement point (8) of the algorithm, assigning the auxiliary variable i the value 2 (i:=2).
Points (9) through (14) can be read as: for successive values of i starting from 2, strike out all multiples of i. Continue striking out until i satisfies the condition: i⋅i>n. The Pascal instruction implementing the pattern "execute until the condition is met" is the repeat instructions until condition loop. This loop ensures the instructions are executed at least once before checking the termination condition.
In Line 15, we start our repeat until loop. In Line 16, we check if the number i has not been struck out previously (9). The condition if not del[i] is met when del[i] is false, meaning i is a prime number, and we must strike out its multiples. The first multiple is i2 (in Line 17, we assign j:=i⋅i) — point (10) of the algorithm.
Points (11) - (12) of the algorithm are realized using a while loop: while j≤n do instruction. As long as the condition is met, the statement after do is executed.
In Line 18, we start the while loop. In Lines 19-20, the instructions executed in the loop are enclosed between begin end. In Line 19, we mark del[j] as deleted (del[j]:=true), and then in Line 20, we increment j to the next multiple of i (j:=j+i) — point (12) of the algorithm. In Line 21, the keyword end closes the logical brackets opened in Line 18.
The keyword end in Line 22, in turn, closes the logical brackets started in Line 16 after the if statement.
In Line 23, we implement point (13) of the algorithm: we increase i by 1 (i:=i+1), preparing to check the next number.
Line 24 terminates the repeat until loop. It contains the termination condition i⋅i>n. When the condition is met, the program exits the loop. If not, it returns to Line 16.
Output and Termination
In Line 25, we use a for loop to output all numbers in the range from 2 to n that were not struck out (not del[i]) — the prime numbers.
The keyword end from Line 26 terminates the conditional statement from Line 11, specifically the block contained after the else keyword from Line 12.
The readln instruction in Line 27 has no direct connection with the prime number finding algorithm. It serves to halt the program until the Enter key is pressed, preventing the program window from closing immediately.
The end. instruction in Line 38 terminates the program's operation (algorithm end block (20)).