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

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 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 447090, https://doi.org/10.1007/bf01932283
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 330021, https://doi.org/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, https://doi.org/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, https://doi.org/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 166168, https://doi.org/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, https://doi.org/10.1145/358527.358540
13. Paul Pritchard, Explaining the wheel sieve, Acta Inform. 17 (1982), no. 4, 477–485. MR 685983, https://doi.org/10.1007/BF00264164
14. Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332–344. MR 729229, https://doi.org/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, 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