|
Prime sieves using binary quadratic forms
Author(s):
A.
O. L.
Atkin;
D.
J.
Bernstein.
Journal:
Math. Comp.
73
(2004),
1023-1030.
MSC (2000):
Primary 11Y11;
Secondary 11E25
Posted:
December 19, 2003
Retrieve article in:
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.
References:
-
- 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
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:
10.1090/S0025-5718-03-01501-1
PII:
S 0025-5718(03)01501-1
Received by editor(s):
September 7, 1999
Received by editor(s) in revised form:
March 30, 2002
Posted:
December 19, 2003
Additional Notes:
The second author was supported by the National Science Foundation under grant DMS--9600083.
Copyright of article:
Copyright
2003,
A. O. L. Atkin and D. J. Bernstein
|
Comments: webmaster@ams.org