You don't need to calculate the square root. To know whether a number k
is smaller than sqrt(n)
, you only need to calculate l=n//k
and check whether l>k
or not.
This can also be expensive if you need to do it for every k
. However, in the given program, you can also use l*k=n
to check whether k
divides n
.
Write a program using this method to check primality.