= Number-theoretic sieve
A number-theoretic sieve processes many <integers> together by marking or updating those sharing a <divisor>, rather than testing each <integer> independently. The <sieve of Eratosthenes> marks composite multiples of successive <prime numbers>; related sieves accumulate a <smallest prime factor>, <Euler's totient function>, or <Möbius function> for every argument up to a bound. The useful structure is that the multiples of a fixed <integer> form an <arithmetic progression>, so one loop can update all affected entries in an array.
For example, initializing an array to true and then marking $2p,3p,\ldots$ for each surviving <prime number> $p$ leaves precisely the <prime numbers> unmarked, apart from the separately excluded zero and one. Every <composite number> has a <prime factor>, which proves that every composite is eventually removed. Starting the marking at $p^2$ avoids work already performed by smaller <prime numbers>. Different sieves use different update rules and <time complexity> bounds; the name alone does not imply the complexity of the <sieve of Eratosthenes>.
Back to article page
