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

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

Published electronically:
December 19, 2003

MathSciNet review:
2031423

Full-text PDF

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, Richard H. Hudson,*The segmented sieve of Eratosthenes and primes in arithmetic progressions to*, BIT**17**(1977), 121-127. MR**56:5405****3.**Wieb Bosma (editor),*Algorithmic number theory: ANTS-IV*, Lecture Notes in Computer Science, 1838, Springer-Verlag, Berlin, 2000. MR**2002d:11002****4.**Richard P. Brent,*The first occurrence of large gaps between successive primes*, Mathematics of Computation**27**(1973), 959-963. MR**48:8360**. Available from`http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub019.html`**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, Jonathan Sorenson,*A space-efficient fast prime number sieve*, Information Processing Letters**59**(1996), 79-84. MR**97g:11141****7.**Albrecht Fröhlich, Martin J. Taylor,*Algebraic number theory*, Cambridge University Press, Cambridge, 1991. MR**94d:11078****8.**William F. Galway,*Dissecting a sieve to cut its need for space*, in [3] (2000), 297-312. MR**2002g:11176****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, E. M. Wright,*An introduction to the theory of numbers*, 5th edition, Oxford University Press, 1979. MR**81i:10002****11.**Herbert B. Keller, J. R. Swenson,*Experiments on the lattice problem of Gauss*, Mathematics of Computation**17**(1963), 223-230. MR**29:3445****12.**Paul Pritchard,*A sublinear additive sieve for finding prime numbers*, Communications of the ACM**24**(1981), 18-23. MR**82c:10011****13.**Paul Pritchard,*Explaining the wheel sieve*, Acta Informatica**17**(1982), 477-485. MR**84g:10015****14.**Paul Pritchard,*Fast compact prime number sieves (among others)*, Journal of Algorithms**4**(1983), 332-344. MR**85h:11080****15.**Richard C. Singleton,*Algorithm 357: an efficient prime number generator*, Communications of the ACM**12**(1969), 563-564.**16.**J. V. Uspensky, Max A. Heaslet,*Elementary number theory*, McGraw-Hill, New York, 1939. MR**1:38d**

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