Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0564.10006
Lagarias, J.C.; Miller, V.S.; Odlyzko, A.M.
Computing $\pi$ (x): The Meissel-Lehmer method. (English)
[J] Math. Comput. 44, 537-560 (1985). ISSN 0025-5718; ISSN 1088-6842/e

An earlier paper by {\it J. C. Lagarias} and {\it A. M. Odlyzko} [Lect. Notes Math. 1052, 176-193 (1984; Zbl 0536.10008)] described two methods for computing $\pi$ (x), the number of primes $p\le x$. In the present paper an extended account of the first method is given, with an analysis of its complexity. It is also shown how the use of parallel processing affects the complexity; with M RAM (random access machine) parallel processors, where $1\le M\le x\sp{1/3}$, at most $O(M\sp{-1} x\sp{2/3+\epsilon})$ arithmetic operations are needed and at most $O(x\sp{1/3+\epsilon})$ storage locations. Tables of $\pi$ (x), for various values of x from $10\sp{12}$ to $4\times 10\sp{16}$, are given, showing the discrepancies between $\pi$ (x), Li(x), and Riemann's approximation $R(x)=\sum\sp{\infty}\sb{n=1}\mu (n)n\sp{-1} Li(x\sp{1/n})$.
[H.J.Godwin]

MSC 2000:: *11A41 Elementary prime number theory
68Q25 Analysis of algorithms and problem complexity
11A25 Arithmetic functions, etc.
11N05 Distribution of primes

Keywords: computational number theory; counting function; number of primes; algorithm; complexity; parallel processors; Tables

Citations: Zbl 0536.10008

Cited in: Zbl 0869.11068 Zbl 0622.10027

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]