## Abstract

This paper presents a class of algorithms for computing π(x), the number of primes ≤ x. For each b with 0 ≤ b ≤ 1 4 and each ε{lunate} > 0 there is an algorithm A(b,ε{lunate}) which computes π(x) using O(x^{ 3 5}- 2b 5+ε{lunate}) bit operations and uses O(x^{b+ε{lunate}}) bits of storage. In particular one can compute π(x) using O(x^{ 3 5+ε{lunate}}) bit operations and O(x^{ε{lunate}}) space, or using O(x^{ 1 2+ε{lunate}}) bit operations and O(x^{ 1 4}) space. These algorithms are based on numerical integration of certain integral transforms of the Riemann §-function. This technique can be generalized to evaluate many other arithmetic functions, including the functions π(x; k, l) counting the number of primes p ≡ l (mod k) with p ≤ x and the function M(x) which is the partial sum of the Möbius function μ(n) over all n≤ x.

Original language | English (US) |
---|---|

Pages (from-to) | 173-191 |

Number of pages | 19 |

Journal | Journal of Algorithms |

Volume | 8 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1987 |