C++ 筛选法求解 2 到 100 的素数 |21xrx.com

C++ 筛选法求解 2 到 100 的素数

2023-07-12 15:39:05 深夜i -- --

C++ 筛选法素数 2-100

在计算机科学中，判断一个数是否为素数一直是一个重要且被广泛研究的问题。而在数学中，素数是指除了 1 和本身之外没有其他因子的正整数。本文章将介绍使用 C++ 筛选法来求解范围在 2 到 100 的素数问题。

筛选法是一种非常常用的求解素数的方法，它基于一个非常简单的思想：要筛去一个素数的倍数，将这个素数的倍数标记成非素数。具体地说，我们可以按照下面的步骤来实现筛选法求解 2 到 100 的素数：

1. 首先构建一个大小为 100 的布尔数组，表示每个位置的数是否为素数。一开始，我们将每个位置的数都标记为素数。

2. 然后从 2 开始，依次枚举每个数。如果当前数是素数（即数组中当前位置为 true），那么我们就将它的所有倍数（除了它本身）标记为非素数，即将它们在数组中对应的位置改为 false。

3. 最后，我们就可以将所有标记为素数的数输出即可。

下面是具体的 C++ 代码实现：


#include <iostream>
using namespace std;
const int N = 100;
bool isPrime[N + 1];
int main() {
 // 初始化数组
 for (int i = 2; i <= N; ++i) {
  isPrime[i] = true;
 }
 // 筛选素数
 for (int i = 2; i <= N; ++i) {
  if (isPrime[i]) {
   for (int j = i * i; j <= N; j += i) {
    isPrime[j] = false;
   }
  }
 }
 // 输出素数
 for (int i = 2; i <= N; ++i) {
  if (isPrime[i])
   cout << i << " ";
  
 }
 cout << endl;
 return 0;
}

在我们的代码中，我们使用了三个循环：第一个循环用来初始化布尔数组的值，第二个循环用来进行筛选，第三个循环输出素数。需要注意的是，在第二个循环中，我们使用了 i * i 作为起始位置，因为比 i * i 小的 i 的倍数，已经在之前的循环中被标记为非素数了。

使用上述代码，我们可以得到 2 到 100 之间的所有素数列表：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97。

综上所述，使用 C++ 筛选法非常容易求解 2 到 100 的素数问题。除此之外，筛选法还有其它非常实用的应用，比如求解区间内素数个数、判断一个数是否是质数等。因此，掌握筛选法求解素数的技巧，在计算机科学的研究以及实际应用中都具有重要的意义。

上一篇: idea打包java可执行jar包

下一篇: C++11视频教程：学习现代C++编程的完美指南

评论区

()

相似文章