Prime sieves using binary quadratic forms
HTML articles powered by AMS MathViewer
- by A. O. L. Atkin and D. J. Bernstein;
- Math. Comp. 73 (2004), 1023-1030
- DOI: https://doi.org/10.1090/S0025-5718-03-01501-1
- Published electronically: December 19, 2003
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
- Michael Abrash, Zen of graphics programming, Coriolis Group, Scottsdale, Arizona, 1995.
- Carter Bays and Richard H. Hudson, The segmented sieve of Eratosthenes and primes in arithmetic progressions to $10^{12}$, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 2, 121–127. MR 447090, DOI 10.1007/bf01932283
- Wieb Bosma (ed.), Algorithmic number theory, Lecture Notes in Computer Science, vol. 1838, Springer-Verlag, Berlin, 2000. MR 1850596, DOI 10.1007/10722028
- F. E. Ulrich, The problem of type for a certain class of Riemann surfaces, Duke Math. J. 5 (1939), 567–589. MR 48
- Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM 20 (1977), 100–106.
- 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, DOI 10.1016/0020-0190(96)00099-3
- A. Fröhlich and M. J. Taylor, Algebraic number theory, Cambridge Studies in Advanced Mathematics, vol. 27, Cambridge University Press, Cambridge, 1993. MR 1215934
- 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, DOI 10.1007/10722028_{1}7
- William F. Galway, Analytic computation of the prime-counting function, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2001.
- 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
- H. B. Keller and J. R. Swenson, Experiments on the lattice problem of Gauss, Math. Comp. 17 (1963), 223–230. MR 166168, DOI 10.1090/S0025-5718-1963-0166168-5
- Paul Pritchard, A sublinear additive sieve for finding prime numbers, Comm. ACM 24 (1981), no. 1, 18–23. MR 600730, DOI 10.1145/358527.358540
- Paul Pritchard, Explaining the wheel sieve, Acta Inform. 17 (1982), no. 4, 477–485. MR 685983, DOI 10.1007/BF00264164
- Paul Pritchard, Fast compact prime number sieves (among others), J. Algorithms 4 (1983), no. 4, 332–344. MR 729229, DOI 10.1016/0196-6774(83)90014-7
- Richard C. Singleton, Algorithm 357: an efficient prime number generator, Communications of the ACM 12 (1969), 563–564.
- T. Venkatarayudu, The $7$-$15$ problem, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 531. MR 1, DOI 10.1090/gsm/058
Bibliographic 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
- 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.
- © Copyright 2003 A. O. L. Atkin and D. J. Bernstein
- Journal: Math. Comp. 73 (2004), 1023-1030
- MSC (2000): Primary 11Y11; Secondary 11E25
- DOI: https://doi.org/10.1090/S0025-5718-03-01501-1
- MathSciNet review: 2031423