Prime sieves using binary quadratic forms

We introduce an algorithm that computes the prime numbers up to N N using O (N / log ⁡ log ⁡ N) O (N/ 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.