Meissel Formula for Counting # of Primes

Primes, divisors, arithmetic, number properties, ...
Post Reply
mirzauzairbaig
Posts: 7
Joined: Sun Dec 27, 2009 11:35 pm

Meissel Formula for Counting # of Primes

Post by mirzauzairbaig » Sat May 30, 2015 7:00 am

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+c-2)(b-c+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+c-2)(b-c+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

DJohn
Posts: 53
Joined: Sat Oct 11, 2008 11:24 am

Re: Meissel Formula for Counting # of Primes

Post by DJohn » Sat May 30, 2015 7:50 am

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.

mirzauzairbaig
Posts: 7
Joined: Sun Dec 27, 2009 11:35 pm

Re: Meissel Formula for Counting # of Primes

Post by mirzauzairbaig » Sat May 30, 2015 8:12 am

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.
You are right as $\sqrt[3]{1331}=11$ and in my code I do $\pi(x)=\pi(\left\lfloor x \right\rfloor)$.
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.

MuthuVeerappanR
Posts: 392
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Meissel Formula for Counting # of Primes

Post by MuthuVeerappanR » Sat May 30, 2015 12:54 pm

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?
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

mirzauzairbaig
Posts: 7
Joined: Sun Dec 27, 2009 11:35 pm

Re: Meissel Formula for Counting # of Primes

Post by mirzauzairbaig » Sat May 30, 2015 1:14 pm

I will suggest perusing the reference, Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 12-13, 1994. in particular just a few pages of the first chapter (not more than 20) is more than sufficient.

MuthuVeerappanR
Posts: 392
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Meissel Formula for Counting # of Primes

Post by MuthuVeerappanR » Sat May 30, 2015 1:36 pm

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..
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

Post Reply