TOPICS
Search

Sieve


In its simplest form, a sieve successively crosses out members of a list according to a set of rules. The sieve of Eratosthenes generates prime numbers by crossing out their proper multiples. The sieve of Atkin instead uses the parity of selected representation counts for binary quadratic forms and discards candidates divisible by squares of prime numbers. The sieve for lucky numbers deletes terms by position in the current list. The resulting numbers share some asymptotic properties with the prime numbers.

The quadratic sieve and number field sieve are methods for prime factorization. Both seek congruences between squares modulo the integer being factored. The latter gathers relations using arithmetic in number fields (Pomerance 1996).

In analytic number theory, the large sieve bounds sums of squared magnitudes. In its classical additive form, it applies to values of a trigonometric polynomial at separated points.

The Sierpiński sieve and Wallis sieve are fractals constructed by repeatedly removing central triangles and squares, respectively, from the remaining pieces.


See also

Large Sieve, Lucky Number, Number Field Sieve, Prime Number, Quadratic Sieve, Sierpiński Sieve, Sieve of Atkin, Sieve of Eratosthenes, Wallis Sieve

Explore with Wolfram|Alpha

References

Halberstam, H. and Richert, H.-E. Sieve Methods. New York: Academic Press, 1974.Hawkins, D. "Mathematical Sieves." Sci. Amer. 199, 105-112, Dec. 1958.Huskey, H. D. "Derrick Henry Lehmer (1905-1991)." IEEE Ann. Hist. Comput. 17, 64-68, 1995.Lehmer, D. H. "The Sieve Problem for All-Purpose Computers." Math. Tables and Other Aids to Comput. 7, 6-14, 1953.Lukes, R. F.; Patterson, C. D.; and Williams, H. C. "Numerical Sieving Devices: Their History and Some Applications." Nieuw Arch. Wisk. 13, 113-139, 1995.Pomerance, C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485, 1996.Williams, H. C. and Shallit, J. O. "Factoring Integers Before Computers." In Mathematics of Computation 1943-1993: A Half-Century of Computational Mathematics (Vancouver, BC, 1993) (Ed. W. Gautschi). Providence, RI: Amer. Math. Soc., pp. 481-531, 1994.

Referenced on Wolfram|Alpha

Sieve

Cite this as:

Weisstein, Eric W. "Sieve." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Sieve.html

Subject classifications