核心概述
快速筛（线性筛，Euler/Linear Sieve）：在 O(n) 时间内同时生成质数表，并可计算最小质因子 spf、欧拉函数 φ 与莫比乌斯函数 μ；每个合数仅被其最小质因子标记一次。
原文引述
Description: Linear sieve that computes all primes up to n in O(n); can also produce least prime factor (spf), Euler’s totient (phi), and Möbius mu in the same pass. Time: O(n) time, O(n) memory
展开阐述
-
函数/接口（据实现）
- linearSieve(n) → {primes, spf}：返回质数表 primes 与最小质因子数组 spf（spf[x] 为 x 的最小质因子，质数则 spf[p]=p）。
- linearPhiMu(n) → {primes, spf, phi, mu}：在同一轮中计算 φ 与 μ。
-
核心算法（每个合数仅标记一次）
- 维护数组 spf（或 lp）、可选 phi、mu，及质数表 primes。
- 主循环 i=2..n：
- 若 spf[i]==0：则 i 为质数，设 spf[i]=i，primes.push_back(i)；若需要，phi[i]=i−1，mu[i]=−1。
- 遍历质数 p∈primes：
- 若 p>spf[i] 或 i·p>n：break。
- 置 spf[i·p]=p。
- 若计算 φ/μ：
- 若 p==spf[i]（p | i）：phi[i·p]=phi[i]*p；mu[i·p]=0；break（保证 i·p 仅由其最小质因子 p 处理一次）。
- 否则（p ∤ i）：phi[i·p]=phi[i]*(p−1)；mu[i·p]=−mu[i]。
-
输出语义
- primes：升序质数表。
- spf[x]：x 的最小质因子（x=1 时可定义为 1 或 0，视实现）。
- phi[x]：欧拉函数值。
- mu[x]：莫比乌斯函数，取值 ∈ {−1,0,1}。
-
复杂度
- 时间 O(n)，空间 O(n)。
-
使用与注意
- 索引与边界：统一 1..n 的定义，注意 x=0/1 的特判初始化。
- 溢出：i*p 需用 64 位检查上界以避免乘法溢出。
- 若仅需质数且 n 很大，参见082-数论-埃拉托斯特尼筛的分段筛；若需分解多次查询，使用 spf 可 O(log n) 分解每个数，或参见084-数论-因数分解。
- φ/μ 的线性筛适合批量预处理（如多次询问），求单点时亦可用公式或分解（见 095-数论-欧拉函数）。