12940.找素数

题目分析

本题要求统计区间 $[A, B]$ 内的素数个数。数据范围很小（$2 \le A \le B \le 1000$），因此可以直接对区间内的每一个数进行素数判断，并累加计数。

解题思路

根据素数定义：一个大于 $1$ 的正整数，若除了 $1$ 和它本身之外没有其他正约数，就是素数。

要判断一个数 $n$ 是否为素数，最朴素的做法是检查 $2$ 到 $n-1$ 的所有整数，看是否存在 $n$ 的因子。但这样效率较低，可以进行优化：

• 如果 $n$ 有大于 $\sqrt{n}$ 的因子，那么必定对应一个小于 $\sqrt{n}$ 的因子。因此只需检查 $2$ 到 $\lfloor \sqrt{n} \rfloor$ 之间的整数即可。
• 在代码中，循环条件写作 i * i <= n，等价于 i <= sqrt(n)，且避免了浮点数运算。

由于 $A, B$ 最大为 $1000$，遍历区间内所有数并逐个判断完全足够。

算法说明

参考代码的实现步骤如下：

1. 输入两个整数 $a$ 和 $b$，并初始化计数器 $cnt = 0$。
2. 使用 for 循环从 $a$ 遍历到 $b$，对当前数 $n$：
   • 假设 isPrime = true（先认为是素数）。
   • 用内层循环 for (int i = 2; i * i <= n; i++) 检查 $n$ 是否能被 $i$ 整除：
     • 若 n % i == 0，说明 $n$ 有因子，将 isPrime 设为 false 并立即跳出内层循环（break）。
   • 内层循环结束后，若 isPrime 仍为 true，说明 $n$ 是素数，cnt 加一。
3. 遍历结束后，输出统计结果 cnt。

特殊情况：当 $n = 2$ 时，$i$ 从 $2$ 开始，$i\times i=4>2$，内层循环不会执行，isPrime 保持为 true，$2$ 被正确识别为素数，处理无误。

参考代码

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int a = 0, b = 0, cnt = 0;
6    cin >> a >> b;
7    for (int n = a; n <= b; n++) {
8        bool isPrime = true;
9        for (int i = 2; i * i <= n; i++) {
10            if (n % i == 0) {
11                isPrime = false;
12                break;
13            }
14        }
15        if (isPrime)
16            cnt++;
17    }
18    cout << cnt << endl;
19    return 0;
20}

时间复杂度分析

设 $N = B - A + 1$，最大约为 $1000$。
对于每个数 $n$，内层循环次数约为 $\sqrt{n}$，最大 $\sqrt{1000} \approx 32$。
因此整体时间复杂度为 $O(N\sqrt{B})$，在本题数据范围下仅需几千次运算，非常高效。
空间复杂度为 $O(1)$，仅使用了少量变量，满足内存限制。

拓展思考

虽然本题数据较小，试除法完全可行，但如果 $B$ 的范围扩大到 $10^5$ 或 $10^6$，更优的方法是使用埃拉托斯特尼筛法（或线性筛）预处理素数表，再进行区间查询。这样可以做到 $O(B \log\log B)$ 预处理，$O(1)$ 查询。