Prime sieves using binary quadratic forms

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

    Research output: Contribution to journalArticleAcademicpeer-review

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

    Fingerprint

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

    Cite this