筛法的想法

如果只判一个数，$O(\sqrt{n})$ 够用；但要一次求出 1 到 $n$ 里所有质数，逐个判断是 $O(n\sqrt{n})$，太慢了。换个思路：不去问"这个数是不是质数"，而是反过来——把每个质数的倍数统统划掉，划完之后没被划掉的，自然就是质数。

这就是筛法。先假设所有数都是质数，从最小的 2 开始：2 是质数，就把 $4,6,8,\dots$ 全划掉；下一个没被划掉的是 3，把 $6,9,12,\dots$ 划掉；再下一个没被划掉的是 5……

划掉 2 的倍数后，接下来轮到划 3 的倍数（4 已被划掉，跳过）。

bool notPrime[N];   // 初始都是 false，表示"暂定是质数"
notPrime[0] = notPrime[1] = true;

核心洞见：每个合数一定是某个更小质数的倍数，所以按顺序划过去，一个都不会漏。下一节看具体实现和它的复杂度。