Is there any algorithm to calculate the number of divisors that is more efficient than doing prime factorization?
I just noticed that if you have n = (p_1^e_1)*(p_2^e_2)*...(p_k^e_k), where all the p_i's are distinct primes, then the number of divisors of n is equal to SUM_i[1+e_i].
Yep, whoops I meant PRODUCT, not SUM!
- nbsaleLv 62 years ago
I agree with Puzzling that using the prime factorization is already efficient. The number of prime factors and their powers is the critical thing driving the number of factors. The number of factors doesn't depend on the number itself; any number with the same number of primes and the same powers will have the same number of factors, as your formula shows.
BTW, it's not SUM_i[1+e_i]., it's PRODUCT_i[1+e_i].
- PuzzlingLv 72 years ago
The prime factorization algorithm is pretty efficient already. That's the one I see mentioned any time you want to find the number of factors of an integer. I suppose you could use an algorithm to actually find all the factors and count them, but that seems less efficient except perhaps for smaller numbers.Source(s): http://www.gmathacks.com/gmat-math/number-of-facto... https://www.geeksforgeeks.org/find-divisors-natura...