Francais | English | Espanõl

From Wikipedia, the free encyclopedia

In mathematics, a prime sieve or prime number sieve is a type of algorithm for finding prime numbers. There are many prime sieves, but the sieve of Eratosthenes, the sieve of Atkin^[1], and the various wheel sieves^[2] are most common.

A prime sieve works by creating a list of all integers up to a desired limit and progressively removing composite numbers until only primes are left. This is the most efficient way to obtain a large range of prime numbers; however, to find individual prime numbers, direct primality tests are more efficient.

[edit] Complexity

The sieve of Eratosthenes is generally considered the easiest sieve to implement, but it is the slowest to run. It can find all the primes up to N in time O(N), while the sieve of Atkin and most wheel sieves run in sublinear time O(N/log log N). The sieve of Atkin takes space N^1/2+o(1); Eratosthenes' sieve takes slightly less space O(N^1/2). Sorenson^[3] shows an improvement to the wheel sieve that takes even less space at O(N/((log N)^Llog log N) for any L > 1.

[edit] References

1. ↑ A. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Mathematics of Computation 73 (2004), pp. 1023–1030. [4]
2. ↑ Paul Pritchard, "Improved Incremental Prime Number Sieves", Algorithmic Number Theory Symposium 1994, pp. 280–288.
3. ↑ Jonathan P. Sorenson, "Trading Time for Space in Prime Number Sieves", Lecture Notes in Computer Science Vol. 1423 (1998), pp. 179–195.