Prime sieves using binary quadratic forms

Authors:
A. O. L. Atkin and D. J. Bernstein

Translated by:

Journal:
Math. Comp. **73** (2004), 1023-1030

MSC (2000):
Primary 11Y11; Secondary 11E25

Published electronically:
December 19, 2003

MathSciNet review:
2031423

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce an algorithm that computes the prime numbers up to using additions and bits of memory. The algorithm enumerates representations of integers by certain binary quadratic forms. We present implementation results for this algorithm and one of the best previous algorithms.

**1.**Michael Abrash,*Zen of graphics programming*, Coriolis Group, Scottsdale, Arizona, 1995.**2.**Carter Bays and Richard H. Hudson,*The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10¹²*, Nordisk Tidskr. Informationsbehandling (BIT)**17**(1977), no. 2, 121–127. MR**0447090****3.**Wieb Bosma (ed.),*Algorithmic number theory*, Lecture Notes in Computer Science, vol. 1838, Springer-Verlag, Berlin, 2000. MR**1850596****4.**Richard P. Brent,*The first occurrence of large gaps between successive primes*, Math. Comp.**27**(1973), 959–963. MR**0330021**, 10.1090/S0025-5718-1973-0330021-0**5.**Jack Bresenham,*A linear algorithm for incremental digital display of circular arcs*, Communications of the ACM**20**(1977), 100-106.**6.**Brian Dunten, Julie Jones, and Jonathan Sorenson,*A space-efficient fast prime number sieve*, Inform. Process. Lett.**59**(1996), no. 2, 79–84. MR**1409956**, 10.1016/0020-0190(96)00099-3**7.**A. Fröhlich and M. J. Taylor,*Algebraic number theory*, Cambridge Studies in Advanced Mathematics, vol. 27, Cambridge University Press, Cambridge, 1993. MR**1215934****8.**William F. Galway,*Dissecting a sieve to cut its need for space*, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 297–312. MR**1850613**, 10.1007/10722028_17**9.**William F. Galway,*Analytic computation of the prime-counting function*, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2001.**10.**G. H. Hardy and E. M. Wright,*An introduction to the theory of numbers*, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR**568909****11.**H. B. Keller and J. R. Swenson,*Experiments on the lattice problem of Gauss*, Math. Comp.**17**(1963), 223–230. MR**0166168**, 10.1090/S0025-5718-1963-0166168-5**12.**Paul Pritchard,*A sublinear additive sieve for finding prime numbers*, Comm. ACM**24**(1981), no. 1, 18–23. MR**600730**, 10.1145/358527.358540**13.**Paul Pritchard,*Explaining the wheel sieve*, Acta Inform.**17**(1982), no. 4, 477–485. MR**685983**, 10.1007/BF00264164**14.**Paul Pritchard,*Fast compact prime number sieves (among others)*, J. Algorithms**4**(1983), no. 4, 332–344. MR**729229**, 10.1016/0196-6774(83)90014-7**15.**Richard C. Singleton,*Algorithm 357: an efficient prime number generator*, Communications of the ACM**12**(1969), 563-564.**16.**J. V. Uspensky and M. A. Heaslet,*Elementary Number Theory*, McGraw-Hill Book Company, Inc., New York, 1939. MR**0000236**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y11,
11E25

Retrieve articles in all journals with MSC (2000): 11Y11, 11E25

Additional Information

**A. O. L. Atkin**

Affiliation:
Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, Illinois 60607–7045

Email:
aolatkin@uic.edu

**D. J. Bernstein**

Affiliation:
Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, Illinois 60607–7045

Email:
djb@pobox.com

DOI:
https://doi.org/10.1090/S0025-5718-03-01501-1

Received by editor(s):
September 7, 1999

Received by editor(s) in revised form:
March 30, 2002

Published electronically:
December 19, 2003

Additional Notes:
The second author was supported by the National Science Foundation under grant DMS–9600083.

Article copyright:
© Copyright 2003
A. O. L. Atkin and D. J. Bernstein