## Total Number Of Divisors

Moderator: Board moderators

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### Total Number Of Divisors

how to know fastly the number of divisors?
please give me a c++ example.

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.

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### 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!

Hasselli
New poster
Posts: 22
Joined: Mon Apr 16, 2012 8:08 pm
Contact:

### 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
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)
Mir Shahriar Sabuj