I am reading through the Wikipedia article on prime counting.
The following is presented to describe Meissel's approach:
- Let $p_1, p_2, \dots, p_n$ be the first $n$ primes.
- Let $\Phi(m,n)$ be the number of integers $x \le m$ where $\gcd(x,p_n\#)=1$ where $p_n\#$ is the primorial for $p_n$.
I am clear on the first formula:
$$\Phi(m,n) = \Phi(m,n-1) - \Phi(\frac{m}{p_n},n-1)$$
It's the second formula that is giving me trouble:
- For a given integer $m$, let $n = \pi(\sqrt[3]{m})$ where $\pi(x)$ is the prime counting function.
- Let $\mu = \pi(\sqrt{m}) - n$
Then:
$$\pi(m) = \Phi(m,n) + n(\mu + 1) + \frac{\mu^2 - \mu}{2} - 1 - \sum_{k=1}^{\mu}\pi(\frac{m}{p_{n+k}})$$
I can neither understand why this would be true nor why it would be useful in counting primes.
If someone could explain high level why it is true and why it is useful or provide a reference that can help me to understand the second formula, I would greatly appreciate it. The wikipedia article by itself is not clear to me.
Edit: I believe that I am clear on the second formula.
Please let me know if any of my thoughts are incorrect (or if there is a more precise/concise way to say any point):
- $\mu$: the count of primes $p_i > p_n$ that divides at least one semiprime $\le m$
- $\sum\limits_{k=1}^{\mu}\pi(\frac{m}{p_{n+k}})$: the number of ways to form semiprimes $\le m$ which are divisible by some prime $p$ where $\sqrt[3]{m} < p \le \sqrt{m}$
- $\Phi(m,n)-1$: the count of primes and semiprimes $\le m$ where each lpf $\ge p_{n+1}$.
- $\dfrac{\mu^2 - \mu}{2}$: number of nonsquare semiprimes composed of primes $p_i,p_j$ where $p_n < p_i,p_j \le \sqrt{m}$
- $n(\mu + 1)$: the first $n$ primes + the number of semiprimes $\le m$ where $lpf \le p_n$ and gpf$ > p_n$