More Prime-Counting Functions

July 26, 2011

In the previous exercise we studied Legendre’s prime-counting function. In today’s exercise we will look at two more prime-counting functions, one from Ernst Meissel in the late 1800s and the other from Derrick Lehmer in the mid 1990s.

Both formulas are based on Legendre’s original formula; in both cases, they simply rearrange the terms of Legendre’s formula to eliminate some work. We won’t try to give derivations, as they are complex and chock-full of Greek letters; if you are interested, Hans Riesel’s book Prime Numbers and Computer Methods for Factorization was the source for all three formulas.

Meissel: $\pi(x) = \phi(x, c) + \frac{(b+c-2)(b-c+1)}{2} - \sum_{i=c+1}^b \pi\left(\left\lfloor\frac{x}{p_i}\right\rfloor\right)$ , where $b = \pi(\lfloor \sqrt{x} \rfloor)$ and $c = \pi(\lfloor \sqrt[3]{x} \rfloor)$

Lehmer: $\pi(x) = \phi(x, c) + \frac{(b+a-2)(b-a+1)}{2} - \sum_{i=a+1}^b \pi \left( \left\lfloor \frac{x}{p_i} \right\rfloor \right) - \sum_{i=a+1}^c \sum_{j=i}^{b_i} \left( \pi \left( \left\lfloor \frac{x}{p_i p_j} \right\rfloor \right) - (j-1) \right)$ , where $a = \pi(\lfloor \sqrt[4]{x} \rfloor)$ , $b = \pi(\lfloor \sqrt{x} \rfloor)$ , $c = \pi(\lfloor \sqrt[3]{x} \rfloor)$ , and $b_i = \pi(\lfloor \sqrt{x / p_i} \rfloor)$ for $a < i <= c$ .

Your task is to implement the prime-counting functions of Meissel and Lehmer, then compare timings with Legendre's prime-counting function of the previous exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Like this:

Be the first to like this post.

Pages: 1 2

Posted by programmingpraxis

Filed in Exercises

3 Comments »

3 Responses to “More Prime-Counting Functions”

Graham said
July 26, 2011 at 1:26 PM
I think your write-up of Lehmer’s formula on the first page doesn’t match your code on the second. Specifically, what is b_i supposed to be? And is the fraction out front (b + a - 2) * (b - a + 1) / 2 or (b + c - 2) * (b - c + 1) / 2?
programmingpraxis said
July 26, 2011 at 1:53 PM
Oops. I didn’t do that very well, did I? It’s now fixed.

b_i = pi(isqrt(x/p_i) for a<i<=c

The fraction is (b+a-2)(b-a+1)/2
Graham said
July 26, 2011 at 2:38 PM
I’m completely off my game; Python is either giving me nonsense or complaining of exceeding the recursion depth. I’m going to start over, so I won’t have a solution for a bit.

S	M	T	W	T	F	S
« Jun				Aug »
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

Programming Praxis