Determine the number of factors for extremely large numbers.

1.8k Views Asked by At

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them?

Even an estimation would help as long as it has some relevance to the number in question.

2

There are 2 best solutions below

0
On BEST ANSWER

As others have noted, there are bounds. But you can have, say, two 1000-digit numbers, differing only in their 778th digit, one of the numbers having zillions of factors, the other being prime, or a product of two primes. There is, in general, no way to get much information about the number of possible factors (or odd factors, or even factors, or prime factors, or repeated factors, etc., etc.) without factoring the number.

0
On

If the prime factorization of $N$ is $p_1^{d_1} \ldots, p_n^{d_n}$, then $N$ has $(d_1+1)\ldots(d_n+1)$ divisors. This number of divisors is denoted $d(N)$. A crude upper bound on $d(n)$ is $2 \sqrt{ n}$. A better estimate is

$\log d(n) \le \dfrac{\log n}{\log \log n} (\log 2 + O(1/\log\log n))$