题解

题目解析

• 输入输出：输入两个正整数 $A$ 和 $B$，表示闭区间 $[A, B]$；输出该区间内素数的个数 $C$。
• 数据范围：$2 \leq A \leq B \leq 1000$，区间长度不超过 $1000$，数值规模较小。
• 复杂度要求：时间复杂度 $O\left((B-A+1) \cdot \sqrt{B}\right)$，最坏情况约 $3 \times 10^4$ 次运算；空间复杂度 $O(1)$。
• 算法知识点：素数判定、试除法、区间枚举

思路解析

1. 素数判定（试除法）：对于待判定整数 $x$，只需检查 $2$ 到 $\sqrt{x}$ 之间是否存在因子。若存在则 $x$ 为合数，否则为素数。代码中使用 i * i <= x 避免浮点开方运算，提升效率并保证精度。
2. 区间遍历：在 $[A, B]$ 范围内逐个枚举整数，对每个数调用判定函数，统计返回 true 的次数。
3. 边界处理：题目保证 $A \geq 2$，无需处理 $1$ 的特殊情况；判定函数从 $2$ 开始枚举，自然排除 $1$ 的干扰。

完整代码

#include <bits/stdc++.h>
using namespace std;

// 试除法判定素数：检查2到√x之间是否存在因子
bool find(int x) {
    // i*i <= x 等价于 i <= sqrt(x)，避免浮点运算
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) 
            return false;  // 发现因子，非素数
    }
    return true;  // 无因子，是素数
}

int main() {
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    
    // 枚举区间[a, b]内的每个数
    for (int i = a; i <= b; i++) {
        if (find(i)) 
            cnt++;
    }
    
    cout << cnt << endl;
    return 0;
}