算法概述
线性筛（Linear Sieve），又称欧拉筛，是一种在 $O(n)$ 时间内筛出所有素数并同时预处理积性函数的算法。与经典的埃拉托斯特尼筛（$O(n \log \log n)$）相比，线性筛不仅复杂度更优，还能在筛的过程中顺便计算出所有数的最小质因子、欧拉函数 $\varphi(n)$、莫比乌斯函数 $\mu(n)$ 等重要的数论函数。它是算法竞赛中处理数论问题的核心基础工具。
核心思想
为什么线性筛是线性的？
传统筛法对每个合数可能被多次标记（如12被2和3各标记一次），而线性筛的核心保证是：每个合数只被它的最小质因子筛掉一次。
具体策略：
1. 维护一个质数列表 primes
2. 对于每个数 $i$，依次用 primes 中的质数 $p$ 去筛
3. 如果 $p$ 是 $i$ 的最小质因子（即 $i \mod p == 0$），则停止
这样，对于任意合数 $n = p \times k$（$p$ 是 $n$ 的最小质因子），它只会在 $i = k$、$p$ 为当前质数时被筛一次。
积性函数的同步计算
积性函数满足：若 $\gcd(a, b) = 1$，则 $f(ab) = f(a)f(b)$。
线性筛过程中可以同步维护积性函数：
– 欧拉函数 $\varphi(n)$：小于等于 $n$ 且与 $n$ 互质的正整数的个数
– 莫比乌斯函数 $\mu(n)$：用于容斥和莫比乌斯反演
– 约数个数 $d(n)$、约数和 $\sigma(n)$ 等
Java 完整实现
import java.util.*;
/**
* 线性筛（欧拉筛）完整实现
* 同步预处理：素数表、最小质因子、欧拉函数、莫比乌斯函数、约数个数、约数和
*/
public class LinearSieve {
static final int MAXN = 10000005;
// 核心数组
static boolean[] isComposite; // 是否为合数
static int[] primes; // 素数列表
static int primeCount; // 素数个数
static int[] spf; // 最小质因子 (smallest prime factor)
// 积性函数
static int[] phi; // 欧拉函数
static int[] mu; // 莫比乌斯函数
static int[] d; // 约数个数
static long[] sigma; // 约数和
static int[] powP; // 最小质因子的最高次幂
static int[] cntP; // 最小质因子的指数
/**
* 线性筛核心算法
* 在O(n)时间内筛出素数，并同步计算所有积性函数
*/
static void sieve(int n) {
isComposite = new boolean[n + 1];
primes = new int[n + 1];
spf = new int[n + 1];
phi = new int[n + 1];
mu = new int[n + 1];
d = new int[n + 1];
sigma = new long[n + 1];
powP = new int[n + 1];
cntP = new int[n + 1];
primeCount = 0;
phi[1] = 1;
mu[1] = 1;
d[1] = 1;
sigma[1] = 1;
for (int i = 2; i <= n; i++) {
if (!isComposite[i]) {
// i是素数
primes[primeCount++] = i;
spf[i] = i;
// 素数的积性函数值
phi[i] = i - 1; // φ(p) = p - 1
mu[i] = -1; // μ(p) = -1
d[i] = 2; // d(p) = 2 (1和p)
sigma[i] = 1L + i; // σ(p) = 1 + p
powP[i] = i; // p^1
cntP[i] = 1; // 指数为1
}
// 用已知的素数去筛
for (int j = 0; j < primeCount && i * primes[j] <= n; j++) {
int p = primes[j];
int ip = i * p;
isComposite[ip] = true;
spf[ip] = p;
if (i % p == 0) {
// p是i的最小质因子，即 i = p^k * m, gcd(p, m) = 1
// 此时ip = p^(k+1) * m
// 欧拉函数：φ(ip) = φ(i) * p (因为p | i)
phi[ip] = phi[i] * p;
// 莫比乌斯函数：μ(ip) = 0 (因为p^2 | ip)
mu[ip] = 0;
// 约数个数：d(ip) = d(i) / (cntP[i] + 1) * (cntP[i] + 2)
cntP[ip] = cntP[i] + 1;
powP[ip] = powP[i] * p;
d[ip] = d[i] / cntP[ip] * (cntP[ip] + 1);
// 约数和：σ(ip) = σ(i) + powP[ip] * (sigma[i / powP[i]])
// 简化为：sigma(ip) = sigma(i) * (1 + p + ... + p^(k+1)) / (1 + p + ... + p^k)
// = sigma(i) + powP[ip] * (如果i有m部分，则sigma(m))
long sigmaM = sigma[i] / ((1L * powP[i] * p - 1) / (p - 1));
// 实际上更简单的方式：
sigma[ip] = sigma[i] + powP[ip] * (sigma[i] / ((1L * powP[i] - 1) / (p - 1)));
// 关键：保证每个数只被筛一次
break;
} else {
// p不是i的因子，即 gcd(i, p) = 1
// ip是新的组合，利用积性性质
// 欧拉函数：φ(ip) = φ(i) * φ(p) = φ(i) * (p - 1)
phi[ip] = phi[i] * (p - 1);
// 莫比乌斯函数：μ(ip) = μ(i) * μ(p) = -μ(i)
mu[ip] = -mu[i];
// 约数个数：d(ip) = d(i) * d(p) = d(i) * 2
cntP[ip] = 1;
powP[ip] = p;
d[ip] = d[i] * 2;
// 约数和：σ(ip) = σ(i) * σ(p) = σ(i) * (1 + p)
sigma[ip] = sigma[i] * (1 + p);
}
}
}
}
/**
* 更简洁的线性筛实现（只保留核心逻辑）
*/
static void sieveSimplified(int n) {
isComposite = new boolean[n + 1];
primes = new int[n + 1];
phi = new int[n + 1];
mu = new int[n + 1];
primeCount = 0;
phi[1] = 1;
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!isComposite[i]) {
primes[primeCount++] = i;
phi[i] = i - 1;
mu[i] = -1;
}
for (int j = 0; j < primeCount && i * primes[j] <= n; j++) {
int p = primes[j];
isComposite[i * p] = true;
if (i % p == 0) {
phi[i * p] = phi[i] * p;
mu[i * p] = 0;
break;
} else {
phi[i * p] = phi[i] * (p - 1);
mu[i * p] = -mu[i];
}
}
}
}
/**
* 快速幂
*/
static long power(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
/**
* 利用欧拉函数计算逆元：a^(-1) ≡ a^(φ(m)-1) (mod m)，当gcd(a,m)=1
*/
static long modInverse(int a, int mod) {
if (gcd(a, mod) != 1) return -1;
return power(a, phi[mod] - 1, mod);
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
/**
* 莫比乌斯反演应用：计算与n互质且不超过m的正整数个数
* 利用容斥原理 + 莫比乌斯函数
*/
static long coprimeCount(int n, int m) {
// 求[1, m]中与n互质的数的个数
// 设f(d)为[1,m]中gcd(x,n)=d的数的个数
// 设F(d)为[1,m]中d|gcd(x,n)的数的个数 = [m/d] (d|n)
// 由莫比乌斯反演：f(1) = sum_{d|n} μ(d) * F(d)
long result = 0;
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
// d是n的因子
if (d <= m) result += mu[d] * (m / d);
int other = n / d;
if (other != d && other <= m) {
result += mu[other] * (m / other);
}
}
}
return result;
}
/**
* 计算1到n所有数的欧拉函数之和
* 利用性质：sum_{d|n} φ(d) = n
*/
static long sumPhi(int n) {
long sum = 0;
for (int i = 1; i <= n; i++) {
sum += phi[i];
}
return sum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("=== 线性筛与积性函数演示 ===\n");
int n = 100;
sieveSimplified(n);
System.out.println("1到" + n + "的素数列表：");
for (int i = 0; i < primeCount && primes[i] <= n; i++) {
System.out.print(primes[i] + " ");
}
System.out.println("\n共" + primeCount + "个素数\n");
System.out.println("欧拉函数 φ(n)：");
System.out.println("n\tφ(n)\t与n互质的数");
for (int i = 1; i <= 20; i++) {
System.out.printf("%d\t%d\t", i, phi[i]);
for (int j = 1; j <= i; j++) {
if (gcd(j, i) == 1) System.out.print(j + " ");
}
System.out.println();
}
System.out.println("\n莫比乌斯函数 μ(n)：");
System.out.println("n\tμ(n)\t质因子分解");
for (int i = 1; i <= 30; i++) {
System.out.printf("%d\t%d\t", i, mu[i]);
// 简单质因数分解展示
int x = i;
boolean first = true;
for (int j = 0; j < primeCount && primes[j] * primes[j] <= x; j++) {
if (x % primes[j] == 0) {
int cnt = 0;
while (x % primes[j] == 0) {
x /= primes[j];
cnt++;
}
if (!first) System.out.print(" * ");
System.out.print(primes[j]);
if (cnt > 1) System.out.print("^" + cnt);
first = false;
}
}
if (x > 1) {
if (!first) System.out.print(" * ");
System.out.print(x);
}
System.out.println();
}
System.out.println("\n欧拉函数之和（1到" + n + "）：" + sumPhi(n));
System.out.println("理论值 n*(n+1)/2 = " + (1L * n * (n + 1) / 2));
System.out.println("\n与30互质且不超过20的数个数：" + coprimeCount(30, 20));
System.out.println("\n线性筛是处理数论问题的基石，掌握它可以高效解决各类积性函数问题。");
}
}
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 埃拉托斯特尼筛 | $O(n \log \log n)$ | $O(n)$ | 经典方法 |
| 线性筛（欧拉筛） | $O(n)$ | $O(n)$ | 每个合数只被筛一次 |
| 暴力计算欧拉函数 | $O(n \sqrt{n})$ | $O(n)$ | 逐个分解质因数 |
| 线性筛 + 欧拉函数 | $O(n)$ | $O(n)$ | 同步计算 |
积性函数公式速查
| 函数 | 定义 | 素数幂 $p^k$ | 积性公式 |
|---|---|---|---|
| 欧拉函数 $\varphi$ | ${1 \leq x \leq n : \gcd(x,n)=1}$ | $p^k – p^{k-1}$ | $\varphi(ab) = \varphi(a)\varphi(b)$ |
| 莫比乌斯 $\mu$ | 容斥系数 | $\mu(p) = -1, \mu(p^k) = 0 (k>1)$ | $\mu(ab) = \mu(a)\mu(b)$ |
| 约数个数 $d$ | $\sum_{d | n} 1$ | $k + 1$ |
| 约数和 $\sigma$ | $\sum_{d | n} d$ | $\frac{p^{k+1}-1}{p-1}$ |
经典应用场景
- GCD卷积：利用欧拉函数和莫比乌斯函数进行狄利克雷卷积
- 莫比乌斯反演：将复杂的计数问题转化为可计算的求和
- 欧拉定理/费马小定理：利用欧拉函数计算模逆元
- 原根判定：利用欧拉函数判断原根存在性
- 计数问题：如”与n互质的数有多少个”等容斥类问题
扩展：狄利克雷卷积
/**
* 狄利克雷卷积：(f * g)(n) = sum_{d|n} f(d) * g(n/d)
* 线性筛可以高效计算狄利克雷卷积
*/
static long[] dirichletConvolution(long[] f, long[] g, int n) {
long[] h = new long[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
h[j] += f[i] * g[j / i];
}
}
return h;
}
线性筛是数论算法的基石，掌握它意味着你拥有了解决各类数论问题的强大武器。
