Prime sieves using binary quadratic forms

Atkin, A.; Bernstein, D.

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

Prime sieves using binary quadratic forms
HTML articles powered by AMS MathViewer

by A. O. L. Atkin and D. J. Bernstein PDF

Math. Comp. 73 (2004), 1023-1030

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 0000001, DOI 10.1090/gsm/058