Historically, the most efficient way to find all of the small primes (say all those less than
100,000,000) was by using the Sieve of
Eratosthenes. This sieve can be generalized by viewing it as sieving with
the reducible binary quadratic form xy. Atkin and Bernstein suggest
replacing this quadratic form using irreducible quadratic forms such as
4x2+y2. The we can take advantage of result
such as the following.
A squarefree positive integer p congruent to 1 modulo 4 is prime if and
only if there is an odd number of positive solutions to p =
4x2+y2. Atkin and Bernstein [AB99] show that such seives
compete favorably with the Sieve of Eratosthenes both theoretically and in
practice. They suggest an implementation which can enumerate the primes up to
n in O(n/log log n) operations and
n1/2+o(1) bits of memory.
|
