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 smallest prime factor sieve stores the least prime divisor $\mathrm{spf}(n)$ for integers $n\ge 2$ up to a bound $N$. Initialize entries unset; scan primes in increasing order and fill their still-unset multiples. A composite $n$ first marked by $p$ has no smaller prime divisor, so the stored value is correct. For example, repeatedly dividing $84$ by its stored factors gives $84\to 42\to 21\to 7\to 1$, hence $84=2^2\cdot 3\cdot 7$. A table uses $O(N)$ entries and accelerates repeated factorizations; the values at zero and one need a separate sentinel convention.

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.

The wheel modulus is the product $W$ of a chosen finite set of small distinct prime numbers in wheel factorization. Except for those primes themselves, every prime candidate must lie in a residue class coprime to $W$. For $W=2\cdot 3\cdot 5=30$, the allowed residues are $1,7,11,13,17,19,23,29$, repeating every thirty integers. The proportion retained is $\phi (W)/W$. Passing the wheel only avoids these small divisors; it does not certify primality, since composite values such as $49$ still pass.

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.

The Min_25 sieve computes summatory multiplicative functions by isolating weighted prime sums and then restoring composite contributions. A useful basic form applies when $f(p)={\sum }_{r=0}^d{a}_r{p}^r$ for primes $p$, the degree $d$ is small, and values on prime powers can be computed efficiently. The formulas below explain the two stages; optimized implementations differ in scheduling and cost.^[ref]

Use quotient arguments $Q_N=\{\lfloor N/i\rfloor :1\le i\le N\}$. There are $O(\sqrt{N})$ distinct values: indices at most $\sqrt{N}$ contribute that many, and larger indices yield values below $\sqrt{N}$. The floor function identity $\lfloor \lfloor N/i\rfloor /p\rfloor =\lfloor N/(ip)\rfloor$ keeps later quotients in this table.

For each exponent $r$, initialize $G_r(v)={\sum }_{m=2}^v{m}^r$. Process primes $p$ in increasing order, and eligible $v\ge p^2$ in decreasing order, applyingThis removes composites whose smallest prime factor is $p$. The subtraction inside parentheses excludes earlier primes from the possible cofactors. Decreasing $v$ ensures each smaller argument still has its pre-$p$ value. After sieving, $H(v)={\sum }_r{a}_r{G}_r(v)$ is the desired sum of $f$ over primes up to $v$.

To restore composites, let $p_j$ be the $j$th prime and let $T(x,j)$ sum $f(n)$ over $2\le n\le x$ with every prime factor greater than $p_j$. Set $T(x,j)=0$ for $x\le p_j$. Otherwise its prime contribution is $H(x)-H(p_j)$, and addUnique decomposition by smallest prime factor and its full exponent proves this recurrence: mixed numbers use the first term, pure powers use the second. With $p_0=1$, $H(1)=0$ and $f(1)=1$, the answer is $1+T(N,0)$. No complete-multiplicativity assumption is needed.

For the Euler totient function up to six, the prime contribution is $\varphi (2)+\varphi (3)+\varphi (5)=7$. The composites add $\varphi (4)+\varphi (6)=4$, and $\varphi (1)=1$ gives total twelve. This independently chosen small example checks that prime powers and mixed products are both counted once.

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

An odd-only segmented sieve represents only odd integers in each bounded interval, handling the prime two separately. For an odd first represented value $L$, array index $i$ stands for $L+2i$. To mark multiples of an odd prime $p$, begin at the smallest odd multiple at least $\max (L,p^2)$ and advance by $2p$, corresponding to index stride $p$. Base primes up to the square root of the upper endpoint suffice. The segmentation limits working storage while omitting even candidates roughly halves it again. The number one remains nonprime and must be excluded explicitly.

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