Prime sieves using binary quadratic forms

Atkin, A.; Bernstein, D.

doi:10.1090/S0025-5718-03-01501-1

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 $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.

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 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

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
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