Prime sieves using binary quadratic forms

A.O.L. Atkin; D.J. Bernstein

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

Prime sieves using binary quadratic forms

A.O.L. Atkin, D.J. Bernstein

Research output: Contribution to journal › Article › Academic › peer-review

46 Citations (Scopus)

Abstract

We introduce an algorithm that computes the prime numbers up to N using O(N=log logN) additions and N1=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.

Original language	English
Pages (from-to)	1023-1030
Journal	Mathematics of Computation
Volume	73
DOIs	https://doi.org/10.1090/S0025-5718-03-01501-1
Publication status	Published - 2004

Access to Document

10.1090/S0025-5718-03-01501-1

Cite this

@article{dbecd7eddaa746169e573c0a5f5d46cf,

title = "Prime sieves using binary quadratic forms",

abstract = "We introduce an algorithm that computes the prime numbers up to N using O(N=log logN) additions and N1=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.",

author = "A.O.L. Atkin and D.J. Bernstein",

year = "2004",

doi = "10.1090/S0025-5718-03-01501-1",

language = "English",

volume = "73",

pages = "1023--1030",

journal = "Mathematics of Computation",

issn = "0025-5718",

publisher = "American Mathematical Society",

}

TY - JOUR

T1 - Prime sieves using binary quadratic forms

AU - Atkin, A.O.L.

AU - Bernstein, D.J.

PY - 2004

Y1 - 2004

N2 - We introduce an algorithm that computes the prime numbers up to N using O(N=log logN) additions and N1=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.

AB - We introduce an algorithm that computes the prime numbers up to N using O(N=log logN) additions and N1=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.

U2 - 10.1090/S0025-5718-03-01501-1

DO - 10.1090/S0025-5718-03-01501-1

M3 - Article

SN - 0025-5718

VL - 73

SP - 1023

EP - 1030

JO - Mathematics of Computation

JF - Mathematics of Computation

ER -

Prime sieves using binary quadratic forms

Abstract

Access to Document

Fingerprint

Cite this