{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:58:20Z","timestamp":1776866300827,"version":"3.51.2"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"246","license":[{"start":{"date-parts":[[2004,12,19]],"date-time":"2004-12-19T00:00:00Z","timestamp":1103414400000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We introduce an algorithm that computes the prime numbers up to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N\">\n                        <mml:semantics>\n                          <mml:mi>N<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">N<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    using\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis upper N slash log log upper N right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\/<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi>log<\/mml:mi>\n                              <mml:mo>\n                                \u2061\n                                \n                              <\/mml:mo>\n                              <mml:mi>log<\/mml:mi>\n                              <mml:mo>\n                                \u2061\n                                \n                              <\/mml:mo>\n                              <mml:mi>N<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(N\/{\\log \\log N})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    additions and\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper N Superscript 1 slash 2 plus o left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:msup>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mo>\/<\/mml:mo>\n                              <\/mml:mrow>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mi>o<\/mml:mi>\n                              <mml:mo stretchy=\"false\">(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                          <mml:annotation encoding=\"application\/x-tex\">N^{1\/2+o(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    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.\n                  <\/p>","DOI":"10.1090\/s0025-5718-03-01501-1","type":"journal-article","created":{"date-parts":[[2004,4,21]],"date-time":"2004-04-21T12:29:08Z","timestamp":1082550548000},"page":"1023-1030","source":"Crossref","is-referenced-by-count":49,"title":["Prime sieves using binary quadratic forms"],"prefix":"10.1090","volume":"73","author":[{"given":"A.","family":"Atkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Bernstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2003,12,19]]},"reference":[{"key":"1","unstructured":"Michael Abrash, Zen of graphics programming, Coriolis Group, Scottsdale, Arizona, 1995."},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/bf01932283","article-title":"The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10\u00b9\u00b2","volume":"17","author":"Bays, Carter","year":"1977","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)","ISSN":"https:\/\/id.crossref.org\/issn\/0901-246X","issn-type":"print"},{"key":"3","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/10722028","volume-title":"Algorithmic number theory","volume":"1838","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"key":"4","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1215\/S0012-7094-39-00548-X","article-title":"The problem of type for a certain class of Riemann surfaces","volume":"5","author":"Ulrich, F. E.","year":"1939","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"5","doi-asserted-by":"crossref","unstructured":"Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM 20 (1977), 100\u2013106.","DOI":"10.1145\/359423.359432"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0020-0190(96)00099-3","article-title":"A space-efficient fast prime number sieve","volume":"59","author":"Dunten, Brian","year":"1996","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"},{"key":"7","series-title":"Cambridge Studies in Advanced Mathematics","isbn-type":"print","volume-title":"Algebraic number theory","volume":"27","author":"Fr\u00f6hlich, A.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0521438349"},{"key":"8","isbn-type":"print","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/10722028_17","article-title":"Dissecting a sieve to cut its need for space","author":"Galway, William F.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"key":"9","unstructured":"William F. Galway, Analytic computation of the prime-counting function, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2001."},{"key":"10","isbn-type":"print","volume-title":"An introduction to the theory of numbers","author":"Hardy, G. H.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0198531702","edition":"5"},{"key":"11","doi-asserted-by":"publisher","first-page":"223","DOI":"10.2307\/2003839","article-title":"Experiments on the lattice problem of Gauss","volume":"17","author":"Keller, H. B.","year":"1963","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/358527.358540","article-title":"A sublinear additive sieve for finding prime numbers","volume":"24","author":"Pritchard, Paul","year":"1981","journal-title":"Comm. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0001-0782","issn-type":"print"},{"issue":"4","key":"13","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF00264164","article-title":"Explaining the wheel sieve","volume":"17","author":"Pritchard, Paul","year":"1982","journal-title":"Acta Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5903","issn-type":"print"},{"issue":"4","key":"14","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/0196-6774(83)90014-7","article-title":"Fast compact prime number sieves (among others)","volume":"4","author":"Pritchard, Paul","year":"1983","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"15","doi-asserted-by":"crossref","unstructured":"Richard C. Singleton, Algorithm 357: an efficient prime number generator, Communications of the ACM 12 (1969), 563\u2013564.","DOI":"10.1145\/363235.363247"},{"key":"16","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1090\/gsm\/058","article-title":"The 7-15 problem","volume":"9","author":"Venkatarayudu, T.","year":"1939","journal-title":"Proc. Indian Acad. Sci., Sect. A."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2004-73-246\/S0025-5718-03-01501-1\/S0025-5718-03-01501-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2004-73-246\/S0025-5718-03-01501-1\/S0025-5718-03-01501-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T13:44:47Z","timestamp":1776779087000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2004-73-246\/S0025-5718-03-01501-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12,19]]},"references-count":16,"journal-issue":{"issue":"246","published-print":{"date-parts":[[2004,4]]}},"alternative-id":["S0025-5718-03-01501-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-03-01501-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2003,12,19]]}}}