 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,\dots$ 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.