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.
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.