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.

An odd-only sieve stores only odd candidates, handling the prime two separately. This reduces the candidate storage and avoids marking even composites repeatedly.

A totient sieve computes the Euler totient function for many integers at once. Initialize $\varphi (n)=n$ and, for each prime $p$, replace $\varphi (n)$ by $\varphi (n)(1-1/p)$ for every multiple $n$ of $p$.

A number-theoretic sieve used to enumerate prime numbers by excluding composite numbers. The sieve of Eratosthenes marks multiples of each discovered prime, beginning at its square.

Choose a modulus $W$ that is a product of small primes. Every prime not dividing $W$ must be coprime to $W$, so a search can restrict candidates to the corresponding residue classes modulo $W$. For several linear polynomials, discard each residue class in which any required value is divisible by a selected prime. The surviving residue classes can be combined using the Chinese remainder theorem.

A Du Jiao sieve computes a summatory arithmetic function using a Dirichlet convolution identity and memoization of repeated quotient arguments. For the Mertens function $M(n)={\sum }_{k\le n}\mu (k)$, the identity ${\sum }_{d\mid k}\mu (d)=[k=1]$ gives $M(n)=1-{\sum }_{i=2}^{n}M(\lfloor n/i\rfloor )$. Grouping equal quotients and precomputing small arguments makes this recurrence relation useful for large inputs.

A family of algorithms for summatory multiplicative functions that first computes suitable sums over primes at quotient values and then incorporates prime powers. The required prime-sum formulas and complexity depend on the particular multiplicative function.

A number-theoretic sieve that processes a large search range in smaller intervals. To find primes in $[L,H]$, first generate the primes at most $\sqrt{H}$, then mark their multiples in the current segment. Memory for the segment depends on its width rather than on $H$.

A number-theoretic sieve that visits each composite number exactly once, through its smallest prime factor. Keep a growing list of prime numbers; for each $i$, generate $ip$ only for stored primes $p\le \mathrm{spf}(i)$. Each composite $m$ has a unique representation $m=\mathrm{spf}(m)(m/\mathrm{spf}(m))$ admitted by this rule, giving $O(N)$ arithmetic updates up to $N$.