My question stems from a wikipedia article on prime counting.
The details on Meissel's method can be found in the wikipedia article.
As I understand, Meissel proposed two formulas which I asked about in a previous question:
$$\Phi(m,n) = \Phi(m,n-1) - \Phi(\frac{m}{p_n},n-1)$$
$$\pi(m) = \Phi(m,n)+n(\mu + 1) + \frac{\mu^2 - \mu}{2} - 1 - \sum_{k=1}^{\mu} \pi(\frac{m}{p_{n+k}})$$
The wikipedia article says that in 1959, "Derrick Henry Lehmer extended and simplified Meissel's methods."
Here's the simplification as I understand it:
- Let $m$ be any real number.
- Let $P_k(m,n)$ be the number of numbers not greater than $m$ with exactly $k$ prime factors all greater than $p_k$.
- Let $P_0(m,n) = 1$
- Let $y$ denote an integer where $\sqrt[3]{m} \le y \le \sqrt{m}$
- Let $n = \pi(y)$ where $\pi(y)$ is the prime counting function.
Then:
$$\pi(m) = \Phi(m,n) + n - 1 - P_2(m,n)$$
with:
$$P_2(m,n) = \sum_{y < p \le \sqrt{m}}(\pi(\frac{m}{p}) - \pi(p)+1)$$
Here are my questions:
If we can set $y$ to any value such that $\sqrt[3]{m} \le y \le \sqrt{m}$, why not set $y = \sqrt{m}$. Is there any advantage to using $y < \sqrt{m}$?
Is the major simplification that the number of iterations in $\sum\limits_{y < p \le \sqrt{m}}\left(\pi(\frac{m}{p}) - \pi(p)+1\right)$ is less than the number of iterations in $\sum\limits_{k=1}^{\mu} \pi(\frac{m}{p_{n+k}})$?
Is there any other reason that the Lehmer's method represents a simplification over Meissel's method.
Edit: I found that the wikipedia article is largely based on this well-written AMS.org article (which is referenced in the Wikipedia article).
My questions stem from information that is missing in the wikipedia article which is found in the AMS.org article.
If no one answers my question, I will make an attempt to answer my own question based on the details provided in the AMS.org article.