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.