There are various ways of finding divisors of a number. The most intuitive and basic approach can be
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
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
![About [span]me[/span]](https://igcdn-photos-h-a.akamaihd.net/hphotos-ak-xpa1/t51.2885-19/s150x150/12568736_762288483902447_81636589_a.jpg)
