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.