Thread: Reducing number of divisions!

Hi all,this is my first post on the forum. I am solving a programming problem where I need to find factors of a big number N(can be even or odd). The problem is:
I need to test different i such that (N-i) is divisible by i+1
For a number as large as 100 crores it would take a lot of time. And therefore I need some method by which I am able to reduce the divisions to 100000 or 1000000 at maximum. Is there any way this is possible. Any suggestions would be greatly appreciated.

if then .
so if then .

so it just boils down to find the number of divisors of N+1.

Thanks a lot.. with your method the number of computations reduced from 25 crore divisions to 46000 divisions.. This forum is great..

You really only need to check division by prime numbers less than . Furthermore, each time you find a prime, p, that divides N, you get "p divides into N M times" and now you can switch from finding prime divisors of N to finding prime divisors of M, still larger thah or equal to p.

Do you want prime factors of N or all ways of factoring M? If the latter, first find the prime factors, then start combining them.

For example, to find factors of 186, does 2 divide it? Yes, 186/2= 93. Does 2 divide 93? No. Does 3 divide 93? Yes, 93= 3(31). Does 3 divide 31? No. Does 5 divide 31? No. Since 6 is larger than sqrt{31}, we can stop there. The prime factors of 186 are 2, 3, and 31. Other factors are 1 (of course), 2(3)= 6, 2(31)= 62, and 3(31)= 93.