There are two ways to find prime numbers:

var n,m,p,i,k:longint; f:boolean; begin read(n); read(m); k:=0; for p:=n to m do begin f:=true; i:=2; while (i*i<=p) and f do if p mod i=0 then f:=false else i:=i+1; if f then begin writeln(p); k:=1; end; end; if k=0 then writeln('Absent'); end.

and

 var n,m,p,i,k:longint; f:boolean; begin read(n); read(m); k:=0; for p:=n to m do begin f:=true; i:=2; while (i<=sqrt(p)) and f do if p mod i=0 then f:=false else i:=i+1; if f then begin writeln(p); k:=1; end; end; if k=0 then writeln('Absent'); end.

Please explain what the condition (i * i <= p) means in the first implementation? I understand that it works faster, I want to understand why.

  • sorry, it’s not obvious to you that a*a <b and a < sqrt(b) equivalent? And they work under normal compilation in the same way (within the limits of error). - pavel
  • Pavel, then the question in the forehead, the teacher asks to explain why when searching for numbers in the range (from 300 000 - 1 000 000), the first implementation is more optimal? - Malawar Olberg
  • five
    I think the teacher wants to get the following answer. "Because the multiplication operation * is faster than taking the square root of sqrt . Multiplication can be performed with a single processor command, and the square root is a complex and lengthy iterative operation." But in general, it seems that the teacher simply does not know that the modern mathematical coprocessor is able to calculate the square root at the same speed as the multiply. - user194374
  • five
    @kff and the normal compiler will make a calculation before the loop, so the operation will be performed | len | operations, and the order loop itself | len sqrt M | and against this background, it’s all the same how to count ... And yes, I completely agree, the root can be calculated in 2-3 multiplication operations. - pavel
  • one
    @kff square root cannot be calculated at the same rate as multiplication. The slowdown will be anyway. - Pavel Mayorov

2 answers 2

I think the teacher wants the following answer:

"Because the multiplication operation * is faster than taking the square root of sqrt. Multiplication can be performed with a single processor command, and the square root is a complex and lengthy iterative operation."

But in general, it seems that the teacher simply does not know that the modern mathematical coprocessor is able to calculate the square root at the same speed as the multiply.
- kff

@kff and the normal compiler will make a calculation before the loop, so the operation will be performed | len | operations, and the order loop itself | len sqrt M | and against this background, it’s all the same how to count ... And yes, I completely agree, the root can be calculated in 2-3 multiplication operations.
- pavel

From myself, I note that, at least when working with numbers with a dot, in cycles, multiplication is still faster than extracting the root.

  • one
    “A modern mathematical coprocessor is capable of calculating a square root at the same rate as multiplying” - uh ... but multiplication is integer, and taking a root is not. - Qwertiy ♦

In theory, integer multiplication is faster than operations on fractional numbers — in this case, extracting the root. But this is not the only reason. Especially, the calculation of the root can be made before the cycle, since the cycle p does not change. And we get one operation instead of a heap of multiplications in a cycle.

I don’t know Pascal, but suppose that a 64-bit integer type is used for numbers.
When we extract the square root, the number is given in real double precision. There are 53 significant bits, not 64. Oops. This is a potential bug of the second algorithm. Although with integer multiplication we should take care of the absence of overflow.

On the values ​​(2 27 +1) 2 = 18014398777917441 and (2 30 +1) 2 = 1152921506754330625, the bug does not appear. Frankly speaking, I am not sure whether it is possible to choose a number that is a complete square, so that the square root of it, reduced to double, is strictly less than the original. But if it succeeds, it will mean that the second algorithm contains an error. Therefore, there is usually something else added to accurately capture the root.

Yes, as for the algorithm itself - there are a lot of places that can be optimized. If we have already determined that the number is not prime, it is not advisable to check its further divisors. The only even simple is 2, all other even ones can not be checked. As well as not to check the even divisors.

And you can also implement an algorithm based on the sieve of Eratosthenes. On the basis, because here the interval is set, not starting at 1.