Prime numbers are essential in many fields of mathematics
and computer science, especially cryptography. An interesting problem arises
when we need to decide whether an integer is a prime number.
The straightforward, naïve algorithm for deciding if a
number n is prime follows a procedure in which a loop from 2 to n-1 checks
every time whether the number representing the step of the loop divides n and
in that case returns false.
The previous algorithm runs in O (n). An improvement to the running time of the Naïve prime test can be achieved if we ask ourselves
the question: Is it really necessary to loop from 2 to n-1? The answer to this question is no, is not necessary, it would be enough to loop only from 2 to squart(n).
Correctness of the IsPrime algorithm: Let’s assume that all numbers that divide n are greater than squart(n). If this is the case then
the smallest number that can divide n is squart(n)+1, but, if n is composed then the smallest numbers dividing n must be greater or equal than
[squart(n)+1] [squart(n)+1], but this product is greater than n, which is a contradiction, though there must be at least a number dividing n less than or
equal to squart(n) proving that the IsPrime algorithm will always find a number that divides n if it is composed.