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.

### Like this:

Like Loading...

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?

Cheers!

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! ๐