数论

01 / 共享的机制

很多题目底下其实藏着一层数论结构。一旦看出输入里真正存在的整除性 / 模 / 乘性结构, O(N) 的循环就坍缩成 O(log N) 或 O(N log log N)。三个经典子模式:欧几里得求 GCD、按指数二进制位做快速幂、用素数筛一次性标记所有合数。

01 / 一句话本质

在一次共享扫描中,走遍每个素数的倍数。合数被它的最小素因子最先标记; 素数则存活下来,继续标记自己的倍数。整张表在 O(N log log N) 内填好 —— 每个合数被触碰的次数摊销下来是 O(log log N),不是每个因子各算一次。

题目找出所有不超过 N 的素数N20

先假设 2 到 20 的每个数都是素数。接下来对每个存活素数,沿其倍数把合数标出来。

步

0 / 16

当前素数

—

素数数

—

0 / 16

02 / 模式骨架

# 埃氏筛is_prime[0..N] ← [True] * (N+1)is_prime[0] = is_prime[1] ← Falsefor p in 2..⌊√N⌋:if is_prime[p]:for m in p*p..N step p: # 从 p² 开始 —— 更小的倍数已被更小素数标记is_prime[m] ← Falsereturn [i for i in 2..N if is_prime[i]]

03 / 什么时候用这个模式

"所有不超过 N 的素数"

最经典的用法 —— LC 204。比逐个试除快一个 log 因子;比威尔逊定理快得没法比。只要 N 装得进内存,答案就是它。

"每个数的最小素因子"

线性筛的变体:扫描过程中,第一个把 m 标为合数的素数,就是它的最小素因子。把布尔换成 spf[m],任何数都能在 O(log m) 内分解。

"对大量数做因式分解"

先在 O(N log log N) 里预处理出 spf[],每次查询就靠反复除以 spf[n] 在 O(log n) 完成。值域到 N、查询 Q 次,合计 O(N log log N + Q log N)。

"有某性质的素数计数 / 求和"

只要问题归结为「枚举 N 以内的所有素数」—— 计数、按下标求和、模 k 余 r 的素数 —— 先筛一次,再过滤。别对每个候选独立试除。

04 / 常见坑

内层从 p*2 开始而不是 p*p。

做无用功 —— 任何小于 p*p 的 p 的倍数都含有更小的素因子, 早就被标过了。对 p = 7,你会重复标记 14、21、28、35、42;只有从 49 起,p 才会贡献新的标记。这一优化正是把复杂度卡紧的关键。

ii.

把筛法当成 O(N log N) 而不是 O(N log log N)。

朴素界 Σ N/p, p 为素数, p ≤ N 看上去像调和级数 —— 但只取素数的倒数和是 log log N + O(1)(Mertens 定理),不是 log N。报对界:它在实际跑的规模下,比 N log N 紧很多。

iii.

外层 p 的上界差一。

外层应当让 p 取到包含 ⌊√N⌋ —— 不是严格小于。任何合数 m ≤ N 必有一个素因子 ≤ √m ≤ √N, 所以大于 √N 的素数贡献不出新标记;但当 N 是完全平方时,p = √N 自己还得跑一次。

05 / 去 LeetCode 上练习

四道题。第一题是教科书式筛法;后三题都是同一张预处理表(素数表 / SPF 表)的下游应用 —— 分解因数、乘性计数、按 GCD 分组。

01Count Primes— LC 204中等→02Largest Component Size by Common Factor— LC 952困难→03Prime Arrangements— LC 1175简单→04Number of Different Subsequences GCDs— LC 1819困难→

— / 什么时候用哪个

GCD / LCM

问题核心是整除性时用 —— 公因数、是否互素、最简分数、由 a · b / gcd(a, b) 求 LCM。欧几里得恒等式 gcd(a, b) = gcd(b, a % b) 每一步都呈几何级数下降。

欧几里得 · LC 1071 · LC 1979

模幂

要计算 aⁿ mod M(n 极大)或质数模下的乘法逆元时用。每步把指数减半;n 的二进制位决定哪些平方项会被乘进答案。O(log n) 替代 O(n)。

指数减半 · LC 50 · LC 372

素数筛

需要所有不超过 N 的素数(或所有最小素因子)时用。对每个素数 p, 把它的所有倍数标记为合数;每个合数被标记的次数摊销下来是 O(log log N)。

埃氏筛 · LC 204 · LC 952