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

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

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.


2 thoughts on “Methods to check if a number is prime or not

  1. Wonderful blog! Do you have any hints for aspiring writers?
    I’m hoping to start my own site soon but I’m a little lost on everything.

    Would you propose starting with a free platform like WordPress or go for a paid option? There are so many
    options out there that I’m completely confused .. Any suggestions?

    • I suggest you to start with a free blog on WordPress or any other platform of your choice and only then if you could handle it well, you can take a step ahead of hiring a web address. All The Best! ๐Ÿ™‚

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s