[Legendre's formula](https://mathworld.wolfram.com/LegendresFormula.html) can be very easily be generalised as mentioned [here](https://projecteuler.net/action=redirect;post_id=111677) (visible after login) which is like this


${\pi}(v,p)={\pi}(v,p-1)-1.[{\pi}(v/p,p-1)-{\pi}(p-1,p-1)]$


${ \big\downarrow}$


$S(v,p)=S(v,p-1)-p[S(v/p,p-1)-S(p-1,p-1)]$


This is still $O(n^{3/4})$ algorithm


I have been trying to achieve the same with [Lehmer's formula](https://mathworld.wolfram.com/LehmersFormula.html)


$\pi(n)=φ(n, a)+\frac{1}{2}(b+a-2)(b-a+1)-\sum\_{i=a}^{b}{\pi}(\frac{x}{p\_i})-\sum\_{i=a+1}^c \sum\_{j=i}^{b\_{i}}[{\pi}(\frac{x}{p\_ip\_j})-(j-1)]$


where $b = n^{1/2}, c = \pi(n^{1/3}), a = \pi(n^{1/4}), φ(n,a)-$ **number of integers** in [1;n] such that they are not divisible by any prime among first $a$ primes.


${ \big\downarrow}$


$S(n)=\Phi(n, a)+\frac{1}{2}(\sum b+\sum a-2)(\sum b-\sum a+1)-\sum\_{i=a}^{b}p\_i{S}(\frac{x}{p\_i})-\sum\_{i=a+1}^c \sum\_{j=i}^{b\_{i}}[p\_ip\_j{S}(\frac{x}{p\_ip\_j})-\sum(j-1)]$


The above expression works fine till $n=8$; after that it doesn't.
I am not exactly sure what to do with $\frac{1}{2}(b+a-2)(b-a+1)$ It should not be left as is.
Adding $\sum$ may not be the right way to go.


Then I realised
$\frac{1}{2}(b+a-2)(b-a+1)=a+(a+1)+(a+2)+.......for (b-a) terms$


My required sum should be $\sum a+\sum (a+1)+\sum (a+2)+.......for (b-a) terms$ but even that gives an expression $(b-a)[(a^2+ab+b^2)-1]/6$ which is also giving the correct answer for $n \le 8$.


I have successfully transitioned to from $φ(n, a)$ to $\Phi(n, a)$ where $\Phi(n, a)$ - **sum of integers** in [1;n] such that they are not divisible by any prime among the first $a$ primes.


I guess the equivalent expression of $\frac{1}{2}(b+a-2)(b-a+1)$ should be $s'(a)+s'(a+1)+s'(a+2)+.......for (b-a)$


note: $s'(x)$ is the sum of first $x$ primes; $S(x)$ is the sum of all primes up to $x$.


PS: I am not looking for any suggestion of alternate $O(n^{2/3})$ or similar algos.  

For that I have already gone through [Fastest Algorithm to Compute the Sum of Primes?](https://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes) and more similar literature.  

As a part of this question I am only looking to generalise the Meissel-Lehmer.



How can I convert Meissel's/Lehmer's formula for prime counting to get sum of primes
This might be a "shameless plug" but i did recently "generalize Meissel-Lehmer to count sum of the powers of primes". This was supposed to give an exposition, so it might be of help
<https://arxiv.org/abs/2111.15545>


