C++ 筛选法：求解 100 以内素数 |21xrx.com

C++ 筛选法：求解 100 以内素数

2023-07-13 16:06:15 深夜i -- --

C++ 筛选法 100 素数求解

C++ 筛选法是一种高效的求解素数的方法。该方法基于一个简单的原理，即一个数如果不是素数，一定可以分解为两个数的乘积，其中一个数一定小于它的平方根。因此，我们只需要从小到大判断每个数是否为素数，并记录下已知的素数，然后用已知的素数来筛选后面的数即可。

对于求解100以内的素数，我们可以使用C++语言实现筛选法。首先，我们需要定义一个数组，用来记录每个数是否为素数。然后，我们从2开始，依次判断每个数是否为素数。如果一个数是素数，则将它的倍数标记为非素数。最后，我们可以遍历数组，输出所有标记为素数的数就是100以内的素数了。

以下是C++代码实现：


#include <iostream>
using namespace std;
const int N = 101;
bool is_prime[N]; // 定义数组，记录每个数是否为素数
int main() {
  // 初始化数组
  for (int i = 2; i <= 100; i++) {
    is_prime[i] = true;
  }
  // 筛选素数
  for (int i = 2; i <= 100; i++) {
    if (is_prime[i]) {
      for (int j = i*i; j <= 100; j += i) {
        is_prime[j] = false;
      }
    }
  }
  // 输出素数
  for (int i = 2; i <= 100; i++) {
    if (is_prime[i])
      cout << i << " ";
    
  }
  return 0;
}

以上代码会输出所有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。这些数都只能被1或它本身整除，是数学上非常重要的基本概念。C++筛选法是一种非常高效的求解素数的方法，读者可以按照以上代码实现，深入了解学习。

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

下一篇: C++有哪些编译器？

评论区

()

相似文章