Prime sieves using binary quadratic forms

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

    Research output: Contribution to journalArticleAcademicpeer-review

    37 Citations (Scopus)


    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 languageEnglish
    Pages (from-to)1023-1030
    JournalMathematics of Computation
    Publication statusPublished - 2004


    Dive into the research topics of 'Prime sieves using binary quadratic forms'. Together they form a unique fingerprint.

    Cite this