Distinct number of prime divisors

Question

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.

Answer 1

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<p_i$ for all $i\ge 2$.

Answer 2

Hint. Can you find a useful inequality for the product of $n$ distinct primes?

Answer 3

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.