埃氏筛 · cmm✨ 的算法小课堂

埃拉托色尼筛（Sieve of Eratosthenes）能在 O(n log log n) 时间内找出 [2, n] 内的所有素数。思路朴素而漂亮：

找到一个还没被划掉的数 p，它必然是素数；然后把它的所有倍数（p², p²+p, p²+2p, ...）都划掉。

为什么从 p² 开始？因为 p × k（k < p）一定在某个更小的素数那一轮就被划过了。

实现要点

for (int p = 2; p * p <= n; ++p) {
  if (isPrime[p]) {
    for (int i = p * p; i <= n; i += p) isPrime[i] = false;
  }
}

外层循环只到 √n —— 任何合数 c ≤ n 必有一个因子 ≤ √c ≤ √n，所以 √n 之后的数如果还没被划掉就一定是素数。