Spoj NDIV Approach

What is wrong with this approach :
I am trying to find the count of number of divisors in a-b by using seive , if i found that i is a divisor of j i just update the count of number of divisors of j by 2 because if k if div of n then n/k is also a div of n , and to avoid doing it twice for k and n/k i am using the check operator.

Here is the solution : [1]: http://ideone.com/A8mkR9

1 Like

A great approach dude :slight_smile: but you did a little mistake in your code.

lli check = j/i;
if(check*i == j) // if sqrt(j)==i count only once

Here (check * i == j) is always true. As you want to check if sqrt(j)=i the condition should be if(check == i) because (check == i) iff (j == i * i) .

1 Like

Can someone please explain it in a bit detail ? the methods by which this problem can be solved along with the complexity of the solution :slight_smile: http://www.spoj.com/problems/NDIV/