找素数c++

【问题描述】

小明刚刚学习了素数的概念：如果一个大于 1 的正整数，除了 1 和它自身外，

不能被其他正整数整除，则这个正整数是素数。现在，小明想找到两个正整数A

和B之间（包括A和B）有多少个素数？

【输入描述】

输入 2 行，第一行包含正整数A，第二行包含正整数B。约定 2 ≤ A ≤ B ≤

1000。

【输出描述】

输出一行，包含一个整数C，表示找到C个素数

【样例输入 1】

2
10

【样例输出 1】

4

【样例解释 1】

在 2 和 10 之间有 4 个素数，分别为：2、3、5、7。

【样例输入 2】

98
100

【样例输出 2】

0

【题目大意】

统计整数 A 到 B 范围内的素数个数，数据范围不超过 1000。

【考纲知识点】

多层分支/循环结构（二级）

【解题思路】

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;
}

原文地址：https://blog.csdn.net/D_31415926/article/details/143061514

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！