|
|
In the first line of the program, we include an iostream header file (input/output streams). This is necessary because in the remainder of the program you will want to be able to write on the screen (cout) and load input from the keyboard (cin). In the second line, we include the iomanip header file that we use to format the output. In the third line we tell the compiler that we will use std namespace (cin, cout, endl, setw) namespaces in the namespace program. If we did not do this, we would need to use the longer qualified names (std::cin, std::cout, std::endl, std::setw). In the next line we define the integer constant MAX, which defines the maximum upper limit 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.
In C ++, the program starts with the execution of function main. In our example, this is the only function of the program. Line 6 contains the start of the definition of the main function, this is the beginning of our algorithm (block START (1)). In the next line we declare integer variable n, which we will use in a moment. In C ++, variables can be declared anywhere before they are used, so we do not immediately declare variables here i, j, del which may not be needed at all.
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 specified number exceeds the permissible retention range of the deletion information stored in the short table. In that case, we print out the appropriate message and not 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 C ++, the else keyword may contain exactly one statement that is executed when the condition of the if statement is not fulfilled. When we want to write more instructions here, we need to write them in braces {...} (often called logical braces). In line 12, after the word else, we have enclosed the parentheses { starting the instructions set to be executed when we entered a valid value into variable n. This instructions set ends with only the bracket closing the } of the 27 program lines.
In the remainder of the program, we will use a boolean table, declare it in line 13 before using it. Declaring an array variable we have to specify in the square brackets the number of array elements placed after the variable name. In C ++, the numbering of array elements always starts with 0. If we wanted the number of the last element to be MAX, we would have to declare an array with MAX + 1 elements.
Points (5) to (7) of our algorithm can be read: starting with element 2, ending with element n, assign the each element of the array del false. The implementation of these three points of the algorithm we entered in line 14 of the program. The lower limit of the variable i (the for loop control variable) is set to 2 (for (int i = 2 ... - we declare and initialize the variable i control our loop, the variable i declared here there only within the loop) In the organizational part of the loop there is an instruction executed in turn for each value i: del[i]:=false. In this way we have initialized all the array elements used by the algorithm with a logical value false. It is worth noting here that if n<MAX is not used in the program of the whole array del but only its first n elements and only those elements are initialized. The first two elements of the array (del[0] and del[1]) are also not unused.
In line 15, we declare two integer variables: i and j. At the same time, according to point (8) of the algorithm, we assign the integer variable i value 2. The variable created here has nothing to do with the variable of the same name used to control the loop in the line. 14. That variable was declared inside the for loop and existed only inside this loop, after the execution of the for statement was "forgotten", released.
Points (9) to (14) of the algorithm can be read: for subsequent values of a variable i beginning with 2, delete all multiples of i. Strict until i satisfy i*i>n or otherwise skip as long as i*i<=n. In C ++, the statement that executes the "execute as long as the condition is true" statement is a loop:do statement while (condition)
Executing an instruction between keywords do and while is repeated as long as the condition after the word while is fulfilled. Compliance with this condition is checked every time the instruction is executed, the instruction will be executed at least once (before the first condition check). When the condition is not fulfilled, the program does not return to the start of the loop, but proceeds to execute the remainder of the program that is bound to the while loop. If we have to implement in the loop more instructions we put them in braces.
In line 16, the keyword to start our loop do while and open bracket where we will put instructions in the loop. On line 17 we check the number i have not already been deleted (9). The if !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 deleted is i2 (in line 18 we assign j:=i*i) (see justification for the algorithm description) - point (10) of the algorithm. Points (11) - (12) can be read: until j<=n delete the number j and then increase the value j by i (assign j to the next multiple of the number i). In C ++, the statement that executes the "until the condition is fulfilled execute statement" loop is:while (condition) statement
As long as the condition written after the while keyword is fulfilled, execute the statement. Traditionally, if we need to place more instructions here, we need to store them in the {} brackets.
While in line 19, we begin the while loop, which will be executed for all j values less than n. In lines 20-21, in the brackets {} statements executed in the loop. In line 20, the element with the number j of the array del is set to true, and then in line 21 we increase j to the next multiple of the number i - point (12) of the algorithm. On line 22 we close the brace from line 19.
In line 23, we close the brace starting on line 17 after the if statement to check if the number was already deleted.
In line 24 we make the algorithm point (13), we increment i by 1, thus preparing for the deletion of the multiple of the next number.
Line 25 ends the loop while we draw all multiples of consecutive numbers. It contains the condition of continuing the loop x*x<=n. When the condition is not fulfilled (there is nothing to be left out), the program terminates the loop and proceeds to the instruction in line 26. When the condition is fulfilled, we return to the beginning of the loop to line 17.
In line 26 we write in the for loop all numbers in the range 2 to n, which have not been deleted(!skr[i]) - prime numbers.
Line 27 ends the conditional statement from line 11, part of which is contained after keyword else from line 12.
The instructions in lines 28 - 30 have no relation to the implementation of the division algorithm. They stop the program until you enter any character and press enter to prevent the program window from closing immediately.
The curly brace from line 31 ends the main function and at the same time the entire program (end of algorithm - block (20)).