A Nomad With Compass

for each element x from 1 to N check
if N%x==0 then x is a divisor

This works great for smaller values of n.But as n increases say > 10^5 it tends to take larger time.

After some thinking we can easily deduce that a divisor of a number n will always be <= n/2 . Thus we can modify the above pseudo code to look something like

for each element x from 1 to N/2 check
if N%x==0 then x is a divisor 

Above optimization works well for numbers say <=10^7. But as the limit for n increases above algorithm takes sufficient amount of time for completion.And this logic would definitely result in Time Limit Exceeded in most of the programming portals.

So we need to think a little bit more. suppose we have below equation
a*b=n, then maximum value of a or b will always be less then equal to sqrt(n). (Except for a or b being equal to n/2 or n itself.). Also note that both a and b will be divisor of n . so based on above approach we can modify the algorithm as

for each element x from 1 to <=sqrt(N) do
if N%x==0 then x is a divisor also N/x will be a divisor (see example a*b=n).

Above approach significantly reduces the exceution time of the code. And is one of the fastest ways for determining divisors of a number <=10^9 and runs in just 50-60 msec.


To see the things in action try solving this problem which is based on above concept only CodeForces Problem