3
$\begingroup$

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.

  • 0
    @RaheelKhan, click on my name, you will see my MSE pro$f$il$e$ which discuss$e$s my $e$mail addresses.2012-07-30

2 Answers 2

3

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.

3

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))$