= Solution
Use the <Chebyshev estimate from central binomial coefficients>. Define
$$
\vartheta(x)=\sum_{p\leq x}\log p,\qquad
\psi(x)=\sum_{p^k\leq x}\log p.
$$
The first is the <Chebyshev theta function>; the second counts prime powers with the same logarithmic prime weight. For a positive integer $m$, every prime $m<p\leq2m$ divides $\binom{2m}{m}$, hence
$$
\vartheta(2m)-\vartheta(m)\leq\log\binom{2m}{m}\leq2m\log2.
$$
Summing over dyadic intervals yields $\vartheta(2^j)\leq2^{j+1}\log2$. By monotonicity and rounding $x$ upward to a power of two,
$$
\vartheta(x)\leq Cx,\qquad C=4\log2.
$$
For the lower bound, the central <binomial coefficient> is the largest of the $2m+1$ coefficients whose sum is $4^m$, so
$$
\log\binom{2m}{m}\geq2m\log2-\log(2m+1).
$$
The exponent of a prime in the central coefficient is
$$
\sum_{k\geq1}\left(\left\lfloor\frac{2m}{p^k}\right\rfloor
-2\left\lfloor\frac m{p^k}\right\rfloor\right).
$$
Each summand is zero or one. Therefore $\log\binom{2m}{m}\leq\psi(2m)$. Higher prime powers contribute only
$$
0\leq\psi(x)-\vartheta(x)
=\sum_{k=2}^{\lfloor\log_2x\rfloor}\vartheta(x^{1/k})
\leq C\sqrt x\,\log_2x=o(x).
$$
Combining the lower bound with $2m$ just below $x$ shows $\vartheta(x)\geq cx$ for sufficiently large $x$, with, for example, $c=(\log2)/2$.
Let $\pi(x)$ denote the number of primes at most $x$. Since every prime weight is at most $\log x$,
$$
\pi(x)\geq\frac{\vartheta(x)}{\log x}\geq c\frac{x}{\log x}.
$$
For the upper bound, separate the primes at $\sqrt x$. The small ones number at most $\sqrt x$, and every larger one has weight at least $(\log x)/2$, giving
$$
\pi(x)\leq\sqrt x+\frac{2\vartheta(x)}{\log x}
\leq\sqrt x+2C\frac{x}{\log x}.
$$
Since $\sqrt x=o(x/\log x)$, this proves
$$
\boxed{A\frac n{\log n}\leq N(n)\leq B\frac n{\log n}}
$$
for all sufficiently large $n$, for instance with $A=(\log2)/2$ and $B=8\log2+1$. This elementary <Chebyshev estimate> does not assume the <Prime number theorem>.
Back to article page
