Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Prime sieves using binary quadratic forms


Authors: A. O. L. Atkin and D. J. Bernstein
Translated by:
Journal: Math. Comp. 73 (2004), 1023-1030
MSC (2000): Primary 11Y11; Secondary 11E25
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 $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 [Enhancements On Off] (What's this?)


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: http://dx.doi.org/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
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