Page 1 of 1

Total Number Of Divisors

Posted: Sat Apr 21, 2012 7:28 pm
by Hasselli
how to know fastly the number of divisors?
please give me a c++ example.

Re: Total Number Of Divisors

Posted: Sun Apr 22, 2012 10:27 pm
by SeyedParsa
You can count the devisors between 1 and sqrt(n) and double it.
Then if n is a square number, subtract 1 from the result.

Re: Total Number Of Divisors

Posted: Mon Apr 23, 2012 5:25 am
by Hasselli
Is there any faster way?

Re: Total Number Of Divisors

Posted: Mon Apr 23, 2012 7:55 am
by brianfry713
Find the prime factorization first.

Re: Total Number Of Divisors

Posted: Mon Apr 23, 2012 8:40 pm
by Hasselli
Doesn't it take time as much as Seyedparsa's algorithm?

Re: Total Number Of Divisors

Posted: Mon Apr 23, 2012 9:56 pm
by brianfry713
Checking only primes is faster than checking every integer.

Re: Total Number Of Divisors

Posted: Sat Aug 18, 2012 8:01 pm
by aerofoil.kite
If the prime factorization of an integer is
p1^x1 * p2^x2 * p3^x3 * ... * pn^xn , where, p1, p2, ..., pn are primes,

then the number of divisors is
(x1 + 1) * (x2 + 1) * (x3 + 1) * ... * (xn + 1)