Home computickets Pascal Prime Algorithm

# Pascal Prime Algorithm

Author

Date

Category

Task: find all prime numbers not exceeding the given one. Below is the code. Could you please check if there is an error. I’m not entirely sure if it works correctly. I would be grateful.

``````Program Lab_4;
var
i, n, range: integer;
Flag: boolean;
Begin
i: = 0;
n: = 0;
write ('Enter range:');
while i & lt; range do
Begin
Flag: = True;
n: = 0;
i: = i + 1;
while n & lt; i - 1 do
Begin
n: = n + 1;
if ((i mod n = 0) and (n & gt; 2)) or ((i mod 2 = 0) and (i & lt; & gt; 2)) then
Flag: = False;
end;
if Flag then
writeln (i, '- Prime number!');
end;
end.
``````

Here, take a look. Something like this should be.

``````program Lab_4;
var
i, n, range: integer;
Flag: boolean;
begin
i: = 1;
n: = 0;
write ('Enter range:');
while i & lt; range do
begin
Flag: = True;
n: = 1;
i: = i + 1;
if i & lt; & gt; 2 then
while n & lt; = sqrt (i) do
begin
n: = n + 1;
if i mod n = 0 then begin
Flag: = False;
break;
end;
end;
if Flag then
writeln (i, '- Prime number!');
end;
end.
``````

Sometimes it is much easier to rewrite the code. Then its readability will increase.

Why do you use the `while `loop when `for `is needed here, I did not understand. Well, as you rightly noted, you need to check divisibility not up to the number itself, but up to its square root.

Total:

``````program Lab_4;
var
i, n, range: integer;
Flag: boolean;
begin
write ('Enter range:');
for i: = 2 to range do begin
Flag: = True;
for n: = 2 to Trunc (Sqrt (i)) do begin
Flag: = i mod n & lt; & gt; 0;
if not Flag then
break;
end;
if Flag then
writeln (i, '- Prime number!');
end;
end.
``````

You can check your program for errors in an automated system. For example, here .
True, the I / O of the program will need to be adapted for the testing system, but it’s simple.

You can use the ideas Sundarama , the essence of which is simple and logical.

1. Sift only odd numbers. Those. the sieve element `a [m] `must contain the number `m `and match the number `2m + 1 `.
2. Exclude from the array all numbers of the form i + j + 2ij , since `2 (i + j + 2ij) +1 `= `(2i + 1) ( 2j + 1) `.
This is sufficient since all composite odd numbers are the product of odd numbers.
3. Boundaries for the lower index `i `are determined by the condition (2i + 1) 2 ∈ [3, 2M + 1] , where `M `– dimension of array `a `.
Those. i ∈ [1, sqrt (2M + 1) / 2 -1]
4. Boundaries for the larger index `j `are determined by the condition i + j + 2ij ∈ [1, M] .
Those. j ∈ [1, (M-i) / (2i + 1)] .
5. Enumeration by `i `and `j `is performed with step 1.
6. The `m `values ​​obtained from the selection should be converted to prime numbers using the formula p = 2m + 1 .

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.