Methods to check if a number is prime or not

One of the most common problem a competetive programmer solves is regarding prime numbers. A beginner, in general starts solving such problem by following the definition of prime numbers i.e. a prime number is that which is not divisible by any number other than 1 and itself.
So, following this, the pseudocode will be in this way..

n <- input
i <- 2
while i < n
    if n%i = 0
        "NOT A PRIME"
    i <- i+1
if i = n
    "PRIME"

It has an O(n) complexity. But the competetive programming never would ask a question that allows one to get their code accepted in time limit with such an approach. They would demand a much better approach.

A better approach would let us know the concept that ‘a number is not prime if it has a factor that is less than or equal to square root of n’. With this pseudocode can be..

while i*i <= n   //(loop will be iterated till 'i' is atmost square root of n)
    if n%i = 0
        "NOT A PRIME"
    i <- i+1
if i*i > n
    "PRIME"

This code has a complexity of O(sqrt(n)).

Now just think you need to check a if number of order 10^8 is prime or not, previous approach would take 10^8 iterations in solving. Whereas later takes just around 10^4 iterations in solving your problem.

Advertisements