how to know fastly the number of divisors?
please give me a c++ example.
Total Number Of Divisors
Moderator: Board moderators
-
SeyedParsa
- New poster
- Posts: 2
- Joined: Sat Nov 26, 2011 8:15 pm
Re: Total Number Of Divisors
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.
Then if n is a square number, subtract 1 from the result.
Re: Total Number Of Divisors
Is there any faster way?
-
brianfry713
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: Total Number Of Divisors
Find the prime factorization first.
Check input and AC output for thousands of problems on uDebug!
Re: Total Number Of Divisors
Doesn't it take time as much as Seyedparsa's algorithm?
-
brianfry713
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: Total Number Of Divisors
Checking only primes is faster than checking every integer.
Check input and AC output for thousands of problems on uDebug!
-
aerofoil.kite
- New poster
- Posts: 12
- Joined: Tue Dec 06, 2011 8:59 pm
- Location: Bangladesh
- Contact:
Re: Total Number Of Divisors
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)
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)
Mir Shahriar Sabuj