Algorithm to calculate the number of divisors of a given number

Dmitriy is right that you’ll want the Sieve of Atkin to generate the prime list but I don’t believe that takes care of the whole issue. Now that you have a list of primes you’ll need to see how many of those primes act as a divisor (and how often).

Here’s some python for the algo Look here and search for “Subject: math – need divisors algorithm”. Just count the number of items in the list instead of returning them however.

Here’s a Dr. Math that explains what exactly it is you need to do mathematically.

Essentially it boils down to if your number n is:
n = a^x * b^y * c^z
(where a, b, and c are n’s prime divisors and x, y, and z are the number of times that divisor is repeated)
then the total count for all of the divisors is:
(x + 1) * (y + 1) * (z + 1).

Edit: BTW, to find a,b,c,etc you’ll want to do what amounts to a greedy algo if I’m understanding this correctly. Start with your largest prime divisor and multiply it by itself until a further multiplication would exceed the number n. Then move to the next lowest factor and times the previous prime ^ number of times it was multiplied by the current prime and keep multiplying by the prime until the next will exceed n… etc. Keep track of the number of times you multiply the divisors together and apply those numbers into the formula above.

Not 100% sure about my algo description but if that isn’t it it’s something similar .

Leave a Comment