illegalCreed

中文

English

中文

English

Appearance

入门：素数定义、试除法与筛法动机 ​

基于通用数论概念 · 核于 2026-07

速查 ​

  • 素数定义：大于 1 的自然数，且只能被 1 和自身整除（恰好两个正因子）。2 是最小的素数，也是唯一的偶素数；1 不是素数（因子只有一个）。
  • 合数：大于 1 且不是素数的数（至少有一个 1 和自身之外的因子）；1 既非素数也非合数。
  • 试除法判定（单数）：判定 n 是否为素数，只需试除 2 到 √n 的所有整数——O(√n)；若都除不尽则 n 是素数。
  • 为何只到 √n：因子成对出现，若 n = a × b 且 a ≤ b，则 a ≤ √n；只要 2..√n 都除不尽，√n..n-1 也必然除不尽。
  • 何时用判定、何时用筛：判定单个数用试除法 O(√n) 最划算；要求 [1, n] 内所有素数时，逐个试除是 O(n√n)，必须用筛法批量处理。
  • 筛法本质：开一个长度 n+1 的布尔数组 isPrime，初始全 true，让每个素数去「标记」自己的倍数为合数——剩下的 true 即素数。
  • 埃氏筛：从 2 起，每遇到一个仍为 true 的数 p（即素数），就把 2p、3p、... 全标 false——O(n log log n)，接近线性但有重复（如 12 被 2 和 3 各筛一次）。
  • 线性筛 / 欧拉筛：额外维护素数表，让每个合数只被其最小质因子筛掉一次，通过 i % primes[j] === 0 时 break 实现——严格 O(n)。
  • 复杂度对比：试除判定 O(√n)；埃氏筛 O(n log log n)；线性筛 O(n)；空间均为 O(n)（筛法）。
  • 应用：预处理素数表后 O(1) 查询、用最小质因子表 spf 做 O(log n) 质因数分解、欧拉函数 / 莫比乌斯函数等积性函数筛法。
  • 边界：isPrime[0] = isPrime[1] = false（1 不是素数）；埃氏筛外层只需遍历到 √n（更大的素数没有 ≤n 的倍数未筛）。
  • 进阶顺序：埃氏筛与线性筛详解 → 优化与应用场景 → 参考。

一、素数与合数：定义与边界 ​

素数（prime）是大于 1的自然数里，只能被 1 和自身整除的数——也就是正因子恰好有两个（1 和自己）。前几个素数是 2, 3, 5, 7, 11, 13, ...。注意几个易错点：

  • 2 是最小的素数，也是唯一的偶素数（其他偶数都能被 2 整除，故是合数）。
  • 1 不是素数：它的正因子只有 1 一个（不是「两个」），所以既非素数也非合数。这是筛法初始化 isPrime[1] = false 的依据，也是「算术基本定理」能成立的前提（否则 6 = 2×3 = 1×2×3 = 1×1×2×3 = ... 分解就不唯一了）。
  • 合数（composite）是大于 1 且不是素数的数，即至少有一个「1 和自身之外」的因子，如 4, 6, 8, 9, 10, ...。

算术基本定理：任何大于 1 的整数都能唯一分解为有限个素数的乘积（不计顺序）。这是素数被称为「数论原子」的原因——筛法就是把这些「原子」批量找出来。

二、试除法：判定单个数是否为素数 ​

判定 n 是否为素数，最直接的办法是「试除」：用 2, 3, ..., n-1 逐个除，若都除不尽则 n 是素数。但可以大幅优化——只需试除到 √n：

js
function isPrime(n) {
  if (n < 2) return false;        // 0、1、负数都不是素数
  for (let i = 2; i * i <= n; i++) { // 用 i*i <= n 等价于 i <= √n，避免浮点
    if (n % i === 0) return false; // 找到因子，是合数
  }
  return true;                     // 2..√n 都除不尽，是素数
}

为什么只到 √n ​

因子是成对出现的：若 n = a × b 且 a ≤ b，那么 a × a ≤ a × b = n，即 a ≤ √n。也就是说，n 的较小那个因子一定 ≤ √n。所以只要 2 到 √n 之间没有任何因子，√n 到 n-1 之间也必然没有（若有，它的「配对因子」就在 2..√n 里，已经检查过了）。

  • 复杂度：循环最多 √n 次，故 O(√n)。判定 10¹² 级别的数约 10⁶ 次，毫秒级；但判定 10¹⁸ 级别就要 10⁹ 次，需用 Miller-Rabin 等概率算法。
  • 小优化：单独处理 2 后只试除奇数，常数减半；或只试除 6k±1 形式的数，常数再减。

三、从判定到筛法：为什么需要批量 ​

试除法判一个数很快，但若问题是「求 [1, n] 内所有素数」，逐个试除的总成本是：

判定 2 + 判定 3 + ... + 判定 n  ≈  O(n√n)

n = 10⁶ 时约 10⁹ 次运算，太慢。筛法（sieve）换个思路：不再「逐个判定」，而是用一个数组标记谁是合数，让素数主动去「划掉」自己的倍数。一次预处理就能得到 [1, n] 全部素数，复杂度降到 O(n log log n)（埃氏筛）甚至 O(n)（线性筛）。

筛法用空间换时间：开一个 n+1 的布尔数组 isPrime[0..n]，初始全 true，然后把 0, 1 设为 false，再让每个素数把它的倍数标 false。最后仍为 true 的下标就是素数。

四、两种筛法：埃氏筛与线性筛 ​

埃氏筛：素数筛掉自己的倍数 ​

最直观的筛法，由古希腊学者埃拉托斯特尼提出。从 2 开始遍历，遇到一个仍为 true 的数 p（说明它没被更小的素数筛掉，即素数），就把 2p、3p、4p、... 全部标 false（它们都是 p 的倍数，故是合数）：

js
function eratosthenes(n) {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let p = 2; p <= n; p++) {
    if (!isPrime[p]) continue;        // p 已被筛，是合数，跳过
    for (let k = p * 2; k <= n; k += p) // p 的倍数都是合数
      isPrime[k] = false;
  }
  return isPrime; // isPrime[i] === true 即 i 是素数
}

复杂度 O(n log log n)（一个和 log log n 相关的调和级数，增长极慢，n = 10⁷ 时 log log n ≈ 3，几乎线性）。缺点是有重复：比如 12 = 2×6 = 3×4，会被素数 2 标记一次、又被素数 3 标记一次。

线性筛 / 欧拉筛：每个合数只筛一次 ​

线性筛通过一个约束消除重复——每个合数只被它的最小质因子筛掉。它额外维护一个「已知素数表 primes」，对外层数 i，用 primes 里每个素数 p 去筛 i × p；一旦 i 能被 p 整除（i % p === 0）就 break——这保证 i × p 的最小质因子是 p，不会被后续更大的素数重复筛：

js
function linearSieve(n) {
  const isPrime = new Array(n + 1).fill(true);
  const primes = [];
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);       // i 是素数，入表
    for (const p of primes) {            // 用每个已知素数 p 筛 i*p
      if (p * i > n) break;              // 超出范围
      isPrime[p * i] = false;
      if (i % p === 0) break;            // 关键：保证只被最小质因子筛
    }
  }
  return primes;
}

复杂度严格 O(n)（每个合数只被访问一次），但常数比埃氏筛大（多了素数表和 break 判断）。详见埃氏筛与线性筛详解。

下一步 ​

理解了素数定义、试除判定与筛法动机后，下一步深入两种筛法的实现细节与复杂度证明——为何埃氏筛重复、线性筛如何靠 break 消除重复，见埃氏筛与线性筛：两种筛法详解。