G2003 [GESP202306 二级] 找素数 题解

知识点：枚举、素数判断、循环计数。

解题思路

对闭区间[a,b]逐个试除。若x没有2到√x之间的因数，就把素数计数加1。

为什么正确

合数总有一个不大于平方根的因数，因而试除范围足够判定。

易错点

原题输入区间从2开始；若拓展到1，必须单独排除1。

复杂度

时间O((b-a+1)√b)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,c=0;
    cin>>a>>b;
    for(int x=a;x<=b;x++) {
        bool ok=true;
        for(int i=2;i*i<=x;i++)if(x%i==0)ok=false;
        c+=ok;
    }
    cout<<c;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。