# Bound for number of distinct prime divisors (don't understand the proof)

The task is to determine a bound for the number of distinct prime divisors. The proof can be found here:

The smallest number with $k$ distinct prime divisors is the $k^\text{th}$ primorial. So the most distinct prime divisors for any number up to $x$ will be the the number of divisors of the largest primorial less than or equal to $x$. We know from the primorial asymptotic that this is $\ln(x)\#$. And we know from the Prime Number Theorem that the number of primes less than $\ln(x)$ is $\ln(x)/\ln(\ln(x))$.

Since the upper bound is given by the primorial, we have $\omega(x)\le\omega(x\#)$. By definition, $\omega(x\#)=\pi(x)$. Finally, by the prime number theorem, $\pi(x)\sim x/\ln(x)$. I don't understand how one can conclude that the bound is given by $\ln(x)/\ln(\ln(x))$.

Not $\omega(x)\le\omega(x\#)$, that's an extremely loose bound. The text talks about the largest primorial $\le x$, which isn't $x\#$, but apparently is $\ln(x)\#$. Then $\omega(x)\le\omega(\ln(x)\#)=\pi(\ln(x))\sim \ln(x)/\ln(\ln(x))$.
• Thanks! Do you know why we can use $\ln(x)\#$ instead of $\ln(x\#)$ in the primorial asymptotic? – Anonymous - a group Apr 9 '16 at 11:48
• @Anonymous-agroup: $\ln(x\#)\sim x$ shows that taking the primorial is roughly the inverse of taking the natural logarithm; it doesn't matter whether you first apply the logarithm and then the inverse or vice versa. That's not a rigorous argument, though, since exponentiating an asymptotic equivalence doesn't necessarily result in an asymptotic equivalence. – joriki Apr 9 '16 at 12:10
• $x \# = \prod_{p \le x} p$ and that's the prime number theorem that $\sum_{p \le x} \ln p \sim x$ (the PNT is $\pi(x) = \sum_{p \le x} 1 \sim \frac{x}{\ln x}$ but you prove $\sum_{p \le x} \ln p \sim x$ before) – reuns Apr 9 '16 at 12:53
• @user1952009: That shows that $\ln(x\#)\sim x$; the question was why we can use $\ln(x)\#$ instead. – joriki Apr 9 '16 at 13:02