Computing <IMG ALIGN=MIDDLE >: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Computing : the Meissel, Lehmer, Lagarias, Miller, Odlyzko method

Authors:	M Deleglise J Rivat

Institution:	Département de Mathématiques, Université Lyon 1, 43 Blvd. du 11 Novembre 1918, 69622 Villeurbanne Cedex, France ; Département de Mathématiques, Université Lyon 1, 43 Blvd. du 11 Novembre 1918, 69622 Villeurbanne Cedex, France

Abstract:	Let $\pi(x)$ denote the number of primes $\le x$ . Our aim in this paper is to present some refinements of a combinatorial method for computing single values of $\pi(x)$ , initiated by the German astronomer Meissel in 1870, extended and simplified by Lehmer in 1959, and improved in 1985 by Lagarias, Miller and Odlyzko. We show that it is possible to compute $\pi(x)$ in $O(\frac{x^{2/3}} {\log^2x})$ time and $O(x^{1/3}\log^3x\log \log x)$ space. The algorithm has been implemented and used to compute $\pi(10^{18})$ .

Keywords:

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载免费的PDF全文