Prime sieves using binary quadratic forms

Source abstract

We introduce an algorithm that computes the prime numbers up to N N using O ( N / log ⁡ log ⁡ N ) O(N/{\log \log N}) additions and N 1 / 2 + o ( 1 ) 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.