The Prime Links++ Links related to Prime Numbers
[ Add | Update | New | Popular ]
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.
Top : programs : sieves : binary quadratic
Resources in programs : sieves : binary quadratic
  • Sieve of Atkins - This version generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds. pop
    (Added: 3-Aug-2000 Hits: 18434 Rating: 7.09 Votes: 32) Rate It
Related Topics
Last Updated: 18-Apr-2014
The Prime Pages © 2000-2008
Chris K. Caldwell
more options ...
CGI Powered by Gossamer Threads