Total Number Of Divisors

Let's talk about algorithms!

Moderator: Board moderators

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

Total Number Of Divisors

Post by Hasselli » Sat Apr 21, 2012 7:28 pm

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

Post by SeyedParsa » Sun Apr 22, 2012 10:27 pm

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

Post by Hasselli » Mon Apr 23, 2012 5:25 am

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

Post by brianfry713 » Mon Apr 23, 2012 7:55 am

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

Post by Hasselli » Mon Apr 23, 2012 8:40 pm

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

Post by brianfry713 » Mon Apr 23, 2012 9:56 pm

Checking only primes is faster than checking every integer.
Check input and AC output for thousands of problems on uDebug!

User avatar
aerofoil.kite
New poster
Posts: 12
Joined: Tue Dec 06, 2011 8:59 pm
Location: Bangladesh
Contact:

Re: Total Number Of Divisors

Post by aerofoil.kite » Sat Aug 18, 2012 8:01 pm

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

Post Reply

Return to “Algorithms”