# Distinct number of prime divisors

I am doing some revision, and during an analysis for equality of bit-strings the following lemma is being used -

The number of distinct prime divisors of any number less than $$2^n$$ is at most n.

Why is this true? I have looked around, but most places seem to come to tighter bounds.

EDIT: I some formatting was wrong as i posted the lemma. The exact quote for the lemma is

Lemma 7.4: The number of distinct prime divisors of any number less than $$2^n$$ is at most n.

And is from page 168 in "Randomized Algorithms" by Motwani and Raghavan.

• This is not clear. Did you really mean "any number less than $2$"? And what is $n$ meant to be? If $n$ is the number, then it is clear that there can't be more than $n$ distinct primes dividing it. Was that what you were asking? – lulu Jun 15 at 19:41
• Whatever bound it is that you have in mind, keep in mind that it would suffice to prove a tighter one. – lulu Jun 15 at 19:42
• Edited the post. Wrong formatting. My apologies. @lulu – sn3jd3r Jun 15 at 19:51
• It is easy to prove, because each of the $n$ primes is $\ge 2$ so a product of $n$ of them is $\ge 2^n$. It is also easy to prove rather tighter bounds if you need them, because the product of three primes is at least $30$, for example, rather than $8$. – Mark Bennet Jun 15 at 19:55

Let $$k$$ be a number with $$n$$ distinct prime divisors. Then we have $$k=p_1\cdots p_n\ge p_1\cdots p_1=p_1^n=2^n,$$ where $$p_i$$ is the $$i$$-th prime number. It follows since $$p_1 for all $$i\ge 2$$.
Hint. Can you find a useful inequality for the product of $$n$$ distinct primes?
Because 2 is the lowest prime, it follows $$2^n$$ is the first time a number with prime factors, can have n counted with multiplicities. You can get better bounds. But, this is a greatest lower bound of possibility for n. By Bertrands postulate,it is certain to occur by $$2^{{n^2+n\over 2}}$$ without multiplicities required.