Counting an integer's divisors without just enumerating them (or estimating if not possible)?

Question

I'm trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$.

For example, 28 has six divisors (1, 2, 4, 7, 14, 28). 15 has four (1, 3, 5, 15). I want to, say, figure out how many divisors 242134575355654335549798955848371716626563756785 has.

I'm not trying to factor the integer; I don't care about what two numbers or what three numbers and so on I can multiply to get $n$.

How can I count (or estimate, if need be) the number of divisors an integer has other than by enumerating them? I don't need the actual values for each divisor; I just want to count them faster than by just enumerating them. If that's not possible, I'd be OK with estimating the number of divisors (and, even better, using that estimate to help me find the actual number of divisors).

Answer 1

As far as I know we don't know a smart method of distinguishing between numbers which have $a$ divisors and numbers which have $b$ divisors, unless (say) $a$ is prime (in which case necessarily the number is an $(a-1)$th power of a prime, and we can use root extraction and primality testing). On the other hand, if you factor $n = \prod_i p_i^{d_i}$ then you can compute the number of factors using the formula $\prod_i (d_i + 1)$.

Answer 2

See Yuval Filmus's answer.

Thus, to count an integer's divisors, one can factor that integer into primes.

Although this question is about the number of prime factors, what you're
asking about will be at least as hard as that for cubefree numbers,
regardless of whether or not the prime factors are counted with multiplicity.

Answer 3

The fastest way for not very large integers is to factor into powers of primes. And if you for example factor x = $p^a · q^b · r^c$ for distinct primes p, q, and r, then the number of divisors of x is (a + 1) (b + 1) (c + 1).

To see why: First, if x and y have no common divisors other than 1 then the number of divisors of xy equals the number of divisors of x, times the number of divisors of y. Second, $p^a$ has (a + 1) divisors: 1, p, $p^2$, ..., $p^a$.

To find an upper bound: For example, when factoring you usually continue until you have a prime divisor candidate p, and the remaining unfactored number x is less than $p^2$, so you conclude p is prime. Instead stop factoring when x is less than $p^3$; at that point either x = 1, or x is a prime, or the square of a prime, or the product of two primes, so it has at most four divisors. Assuming it has four divisors instead of continuing to look for factors will give you an upper bound. Or you might stop when $x < p^4$ and conclude that x has at most eight factors, if that is good enough.

Of course you can at some point use some method to either prove that x is prime or that it is composite. If $x < p^3$ has no factors up to p and is composite then it has 4 factors unless x is an exact square.

In general, counting the number of divisors is at least as difficult as testing if a number is prime, since a number is prime iff the number of divisors is 2.

Answer 4

Based on the other answers, there are two plausible approaches:

• Approach 1. Check whether $n$ is prime or not. If it is not, factor it, then use the factorization of $n$ to compute the number of divisors of $n$. (As suggested by Yuval Filmus and Ricky Demer.)

• Approach 2. Check whether $n$ is prime or not. If it is not, find all prime factors that are at most $n^{1/3}$, and write $n=rs$ where all prime divisors of $r$ are at most $n^{1/3}$ and all prime factors of $s$ are larger than $n^{1/3}$. Check whether $s$ is prime or not. Use the known factorization of $r$ and the primality status of $s$ to compute the number of divisors of $n$. (As suggested by gnasher729.)

Approach 1 is asymptotically faster, as I will show below.

In particular, Approach 1 requires factoring arbitrary large numbers. According to current knowledge, the asymptotically fastest algorithm for this is the general number field sieve (GNFS). Its worst-case running time is

$$L_n[1/3, \sqrt[3]{64/9}] = \exp((\sqrt[3]{64/9} + o(1)) (\ln n)^{1/3} (\ln \ln n)^{2/3}).$$

(You can check whether a number is prime or not in polynomial time, and very efficiently in practice, so the time to do that will be far smaller than the time to do everything else.)

Approach 2 requires finding all prime factors of $n$ that are at most $n^{1/3}$. This doesn't necessarily require fully factoring $n$. However, no faster algorithm is known for doing this than to fully factor $n$. According to current knowledge, the asymptotically fastest algorithm for doing this (without trying to fully factor $n$) is the elliptic curve factorization algorithm (ECM). Its worst-case running time is

$$\begin{align*} L_{n^{1/3}}[1/2, \sqrt{2}] &= \exp((\sqrt{2} + o(1)) (\ln n^{1/3})^{1/2} (\ln \ln n^{1/3})^{1/2})\\ &= \exp((\sqrt{2/3} + o(1)) (\ln n)^{1/2} (\ln \ln n)^{1/2}). \end{align*}$$

If you compare the two expressions, you will discover that the former is asymptotically faster.

Moreover, I expect that in practice the crossover point will be at a point where $n$ is small enough that you can fully factor $n$ without too much difficulty, so in practice I expect Approach 1 is reasonable for all ranges of $n$. Therefore, I recommend Approach 1: fully factor $n$, using the best available algorithm for that, and then use its factorization to derive how many divisors it has.