中级 · 筛法

素数计数

读 N,统计 ≤ N 的素数个数。试除法能过(素数判断你做过单个的)— 但 N = 10,000 时,埃拉托斯特尼筛法是"瞬间"和"卡顿"的差别,也是你的第一个"算法即数据结构"的经典。

一句话答案埃氏筛 —— 把每个素数的倍数全部划掉，最后数还剩下几个；N = 10 的答案是 4（2、3、5、7）。

题目

输入: 一个整数 N(1 ≤ N ≤ 10,000)。

输出: 有多少个素数 p 满足 2 ≤ p ≤ N。

样例:

输入	输出	原因
`10`	`4`	2, 3, 5, 7
`1`	`0`	1 不是素数

你的解答

main.cpp — 你的解答

「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 筛法的想法

建 bool is[10001],全部置 true,再 is[1] = false。让 i 从 2 往上走:如果 is[i] 还是 true,i 是素数 — 计数,并划掉它所有的倍数(j = i*i, i*i+i, …)。撑到最后的就是素数。

提示 2 — 两个经典优化

从 i * i 开始划,别从 2 * i:更小的倍数早被更小的素数划过了（6 在 3 之前就被 2 干掉了）。外层走到 i * i <= n 就可以停 — 每个合数必有 ≤ √n 的因数(素数判断里的同款事实)。

题解（先自己试试！）

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool is[10001];
    for (int i = 0; i <= n; i++) is[i] = true;
    is[1] = false;
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (is[i]) {
            count++;
            for (int j = i * i; j <= n; j += i) is[j] = false;
        }
    }
    cout << count << endl;
    return 0;
}

好玩的校验:π(10,000) = 1,229 — 正是判题最大的那个测试点。筛法约 N·log·log N 次操作,试除法约 N·√N:N = 10,000 时是 ~3 万步对 ~100 万步。这个差距 — 以及换来它的布尔数组 — 就是"用内存换时间"的全部思想,算法设计的半壁江山。另一半在欧几里得算法里。

深度解析

为什么这样做对

埃氏筛用内存换时间：不去逐个检验，而是把倍数一个个划掉，O(n√n) 直接压到 O(n log log n)。

代价

O(n log log n) 时间、O(n) 空间。1 万个数只需几千次操作，而不是一百万次。

常见错法

内层从 2*i 开始而不是 i*i，结果对但白做很多功——每个合数被划了好几次。
10^6 的 int 数组放在栈上是 4 MB，已经逼近栈上限。在这个浏览器引擎里要把规模控制住。

下一步

另一个比你的语言还老的算法：最大公约数。

记住这两句

筛法：划掉倍数，不要逐个检验。
用内存换时间，是第一个真正的工程取舍。

🐞 这段是错的 —— 点开,亲手让它挂一次

忘了 is[1] = false，1 被算成素数

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool is[10001];
    for (int i = 0; i <= n; i++) is[i] = true;
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (is[i]) {
            count++;
            for (int j = i * i; j <= n; j += i) is[j] = false;
        }
    }
    cout << count << endl;
    return 0;
}