Problems implementing the Meissel-Lehmer method I'm working on an implementation of the Meissel-Lehmer method for calculating $\pi(x)$. I've figured out how to recursively compute $\phi$, but I'm having trouble with a more basic portion of the code.
On page 3 in https://www.ams.org/journals/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf, it says that $P_2(x,a)$ can be computed in $O(y)$ space by splitting up the sieve of $[1, x/y]$ into blocks of length $y$. The issue is that the sum
$$\sum_{y\leq p\leq \sqrt{x}} \left(\pi\left(\frac{x}{p}\right)-\pi(p)+1\right)$$
seems to require $\pi(n)$ from multiple blocks. For example, if we iterate over primes in $[y, 2y]$, then we will need primes from the last couple blocks, which we haven't computed the sieve for yet. How do I get around this? Or am I misunderstanding the algorithm?
 A: It's not unusual to set $a=\pi(\lfloor n^{1/3}\rfloor)$ and $b=\pi(\lfloor n^{1/2}\rfloor)$ so $P_2$ runs from a to b.  As an aside, note that we might need to recurse to get those values.  We need to sum $\pi(n/p_i)$ for each $a <= i <= b$.  If you run backwards, then you are summing prime counts for growing values, making it a bit clearer that if we remember the last value, then the count to this one is just adding on any primes between the last value ($n/p_{i-1}$) up to the current one ($n/p_i$).  This is where your can use a sieve by blocks.
I found it worked well to precompute some small values using just a sieve, as lots of the first values are tiny.  Once past that threshold the values were far enough apart that I just sieved between the two rather than doing a formal constant block size.  I'd try to get it working first, then go crazy with experiments and optimization.  Followed by Lehmer's method, simple LMO, more complicated LMO, then its extensions if you want.
If n=1,000,000,000 then a=168, b=3401.  Going backwords, this means we start with $p=31607$ therefore we want the prime count of 31638.  This is tiny.  Next we have $p=31601$ so want the prime count of 31644.  If we don't have it in hand, just count primes between the two values.  This is more likely at the end (e.g. when our final two values are $\pi(987166)$ and finally $\pi(991080)$.  It's completely done in something like 0.01s, or 0.8s for $n=10^{12}$.  Kim Walisch's primecount has an even faster Meissel implementation as well as a number of other methods.
