Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce an algorithm that computes the prime numbers up to $N$using $O(N/{\log\log N})$ additions and $N^{1/2+o(1)}$ 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.

References [Enhancements On Off] (What's this?)

  • 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 $10^{12}$, 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
  • 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

Similar Articles

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

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

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

American Mathematical Society