Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
A very crude upper bound for the number of factors of $n$ is$\lfloor \ln_2(n) \rfloor$ (here $\lfloor . \rfloor$ denotes the floor function) : since $n = 2^{\ln_2(n)}$ and each factor of $n$ is $\ge 2$, there can be no more than $\lfloor \ln_2(n) \rfloor$ factors. The only lower bound that works for every number is $1$ (if $n$ is prime, this bound is sharp). –  Joel Cohen Jul 29 '12 at 20:50
Note that in my previous comment, I took "factor" to mean "prime factor" and not "divisor". –  Joel Cohen Jul 29 '12 at 20:59
@JoelCohen: I do not want to discriminate. I'm looking for all possible integer divisors (odd, even, prime, etc.). –  Raheel Khan Jul 29 '12 at 21:07
see mathoverflow.net/questions/43103/… Meanwhile if you email me, you can have a pdf of the 1988 survey by J.-L. Nicolas with these results and explanations. –  Will Jagy Jul 29 '12 at 21:11
@WillJagy: Where should I email you? –  Raheel Khan Jul 30 '12 at 16:54
show 1 more comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.