I have implemented the algorithm for counting $\pi(x)$: which is the # of primes $\leq x$. My method uses the formula of Meissel [1] which states that $\pi(x)=\phi(x,c) + \frac{(b+c2)(bc+1)}{2}  \sum_{c<i\leq b} \pi(\frac{x}{p_i}) $ where $p_i$ is the $i^\textrm{th}$ prime, i.e. $p_1=2,p_2=3,\dots$ and $b=\pi(\sqrt{x})$ and $c=\pi(\sqrt[3]{x})$ and the $\phi(x,c)$ is defined as in [1].
Now for many values my algorithm works fine but for some it doesn't and I am having trouble verifying. I tried to double my calculation by hand and still run into the same error. I get $\pi(1331)=218$ which is $1$ more than the actual value. After debugging my code I see that I get the following:
$\pi(c)=4, \pi(b)=11, \phi(1331,4)=305, \phi(x,c) + \frac{(b+c2)(bc+1)}{2}=357$ and for the summation with index $i$ we get
$i=5: \pi(\frac{1331}{p_i})=30$
$i=6: \pi(\frac{1331}{p_i})=26$
$i=7: \pi(\frac{1331}{p_i})=21$
$i=8: \pi(\frac{1331}{p_i})=19$
$i=9: \pi(\frac{1331}{p_i})=16$
$i=10: \pi(\frac{1331}{p_i})=14$
$i=11: \pi(\frac{1331}{p_i})=13$
This is giving me $218$. Please check and let me know. I can also share my code in Python if needed.
[1] http://mathworld.wolfram.com/MeisselsFormula.html and http://mathworld.wolfram.com/LegendresFormula.html
Meissel Formula for Counting # of Primes

 Posts: 7
 Joined: Sun Dec 27, 2009 11:35 pm
Re: Meissel Formula for Counting # of Primes
I get pi(c) = pi(11) = 5, as pi counts primes less than or equal to x; in this case, 2, 3, 5, 7, 11.

 Posts: 7
 Joined: Sun Dec 27, 2009 11:35 pm
Re: Meissel Formula for Counting # of Primes
You are right as $\sqrt[3]{1331}=11$ and in my code I do $\pi(x)=\pi(\left\lfloor x \right\rfloor)$.DJohn wrote:I get pi(c) = pi(11) = 5, as pi counts primes less than or equal to x; in this case, 2, 3, 5, 7, 11.
The actual issue is that I get $\sqrt[3]{1331}$ to be $10.999999999999998$ which when I take the int(.) or floor(.) of I get $10$ and get a wrong answer. Thanks.

 Posts: 348
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Meissel Formula for Counting # of Primes
That's a coincidence.. I too was trying to create the PrimePi function in C. Unfortunately I am not a good programmer and stuck at caching the values of $\phi(x,a)$. It contains two parameters and confused at how to do it. Can someone help me or better if you can share your C code using the Meissel formula, so that I can properly study it?
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

 Posts: 7
 Joined: Sun Dec 27, 2009 11:35 pm
Re: Meissel Formula for Counting # of Primes
I will suggest perusing the reference, Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 1213, 1994. in particular just a few pages of the first chapter (not more than 20) is more than sufficient.

 Posts: 348
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Meissel Formula for Counting # of Primes
The formula is not a big problem. I get it. But How to do memoization in C with two parameters? especially in this $\phi(x,a)$? I've been searching all day but still not able to get anything that i can understand..
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.