Pattern Guide
Sieve Variants & Multiplicative Functions
"Linear sieve, Euler's totient sieve, Möbius function. Each number factored once."
Beyond the basic Sieve of Eratosthenes: (1) Linear sieve factors each composite exactly once using smallest prime factors — O(n) and gives smallest prime factors for fast factorization. (2) Multiplicative function sieves compute Euler's totient φ(n), Möbius function μ(n), and divisor counts simultaneously. (3) Segmented sieve for ranges [L,R] with large L. Essential for number theory in competitive programming.
Problems you can solve with this pattern
4 problems · click any to start solving
// Linear sieve: O(n), computes spf[], primes[], phi[], mu[]
function linearSieve(n) {
const spf = new Array(n + 1).fill(0); // smallest prime factor
const primes = [];
const phi = new Array(n + 1).fill(0); // Euler's totient
const mu = new Array(n + 1).fill(0); // Möbius function
phi[1] = 1; mu[1] = 1;
for (let i = 2; i <= n; i++) {
if (!spf[i]) { // i is prime
spf[i] = i;
primes.push(i);
phi[i] = i - 1;
mu[i] = -1;
}
for (const p of primes) {
if (p > spf[i] || i * p > n) break;
spf[i * p] = p;
if (i % p === 0) {
phi[i * p] = phi[i] * p; // p | i, so p^2 | ip
mu[i * p] = 0; // p^2 divides i*p
} else {
phi[i * p] = phi[i] * (p - 1); // gcd(i,p)=1
mu[i * p] = -mu[i];
}
}
}
return { spf, primes, phi, mu };
}
// Factorize n using spf in O(log n)
function factorize(n, spf) {
const factors = {};
while (n > 1) {
const p = spf[n];
factors[p] = (factors[p] || 0) + 1;
n /= p;
}
return factors;
}
// Segmented sieve for primes in [L, R]
function segmentedSieve(L, R) {
const limit = Math.ceil(Math.sqrt(R));
const smallPrimes = linearSieve(limit).primes;
const sieve = new Array(R - L + 1).fill(true);
if (L === 1) sieve[0] = false; // 1 is not prime
for (const p of smallPrimes) {
let start = Math.ceil(L / p) * p;
if (start === p) start += p; // don't mark p itself
for (let i = start; i <= R; i += p) sieve[i - L] = false;
}
return sieve.map((isPrime, i) => isPrime ? L + i : 0).filter(Boolean);
}The linear sieve (smallest prime factor sieve) stores spf[n] = smallest prime factor of n. To factor any n: repeatedly divide by spf[n] until 1. O(log n) factorization after O(n) preprocessing. Euler's totient: φ(p) = p-1, φ(p^k) = p^(k-1)(p-1), φ(mn) = φ(m)φ(n) if gcd(m,n)=1. Möbius: μ(n) = 0 if p² | n, else (-1)^(number of prime factors).
// Linear sieve: O(n), computes spf[], primes[], phi[], mu[]
function linearSieve(n) {
const spf = new Array(n + 1).fill(0); // smallest prime factor
const primes = [];
const phi = new Array(n + 1).fill(0); // Euler's totient
const mu = new Array(n + 1).fill(0); // Möbius function
phi[1] = 1; mu[1] = 1;
for (let i = 2; i <= n; i++) {
if (!spf[i]) { // i is prime
spf[i] = i;
primes.push(i);
phi[i] = i - 1;
mu[i] = -1;
}
for (const p of primes) {
if (p > spf[i] || i * p > n) break;
spf[i * p] = p;
if (i % p === 0) {
phi[i * p] = phi[i] * p; // p | i, so p^2 | ip
mu[i * p] = 0; // p^2 divides i*p
} else {
phi[i * p] = phi[i] * (p - 1); // gcd(i,p)=1
mu[i * p] = -mu[i];
}
}
}
return { spf, primes, phi, mu };
}
// Factorize n using spf in O(log n)
function factorize(n, spf) {
const factors = {};
while (n > 1) {
const p = spf[n];
factors[p] = (factors[p] || 0) + 1;
n /= p;
}
return factors;
}
// Segmented sieve for primes in [L, R]
function segmentedSieve(L, R) {
const limit = Math.ceil(Math.sqrt(R));
const smallPrimes = linearSieve(limit).primes;
const sieve = new Array(R - L + 1).fill(true);
if (L === 1) sieve[0] = false; // 1 is not prime
for (const p of smallPrimes) {
let start = Math.ceil(L / p) * p;
if (start === p) start += p; // don't mark p itself
for (let i = start; i <= R; i += p) sieve[i - L] = false;
}
return sieve.map((isPrime, i) => isPrime ? L + i : 0).filter(Boolean);
}- Exactly O(n) operations (vs O(n log log n))
- Computes SPF for O(log n) factorization
- Easily extended to compute φ(n), μ(n), Ω(n), σ(n) simultaneously
Multiplicative function sieve pattern: If f is multiplicative (f(mn)=f(m)f(n) when gcd(m,n)=1), compute during the linear sieve:
- f(p) = f at prime (base case)
- f(p^k) = formula for prime powers
- f(i*p) = f(i) * f(p) if gcd(i,p)=1, else special prime power formula
Möbius function use: Möbius inversion converts sum over divisors to sum over multiples. Core for "counting integers coprime to n" and inclusion-exclusion on divisors.