1 条题解

  • 2
    @ 2024-4-15 19:07:57

    【解题思路】

    1. 枚举 A 到 B ,依次检查每个数是不是素数。
    2. 用变量 isPrime表示当前枚举的数 n 是否为素数,初始化为 true,如果找到了除了 1 和 n 以外的因数,则把 isPrime 赋值为 false
    3. 寻找 n 的因数时,只需要枚举 2 到根号 n 。因为如果 n 有一个大于根号 n 的因数 k ,那么就一定存在一个小于根号 n 的因数 n/k。
    4. 使用变量 cnt 记录素数的个数,最终输出即可。

    【参考程序】

    #include <iostream>
    using namespace std;
    int main() 
    {
        int a = 0, b = 0, cnt = 0;
        cin >> a >> b;
        for (int n = a; n <= b; n++) 
        {
    
            bool isPrime = true;   // 假设初始 isPrime 的值为 true
            // 利用因数成对存在的性质,遍历较小的因数,判断 n 是否为素数
            for (int i = 2; i \* i <= n; i++) 
            {
                if (n % i == 0) 
                {//若发现 n 存在因数,更改标记 isPrime 并跳出循环
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
                cnt++;  //统计素数个数
        }
        cout << cnt << endl;
        return 0;
    }
    
    • 1

    [GESP202306 二级] 找素数

    信息

    ID
    555
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    651
    已通过
    218
    上传者