C++实现100以内素数筛选法 |21xrx.com

C++实现100以内素数筛选法

2023-07-14 12:31:40 深夜i -- --

C++ 素数筛选法 100 实现

素数筛选法是一种经典的算法，可以在一定范围内快速筛选出素数。在100以内，我们可以使用C++编程语言来实现这一算法。

首先，我们需要定义一个bool类型的数组，用于标记每个数字是否为素数。由于0和1不是素数，因此我们可以将它们标记为false。而大于1的数字都可以标记为true。

接下来，我们可以采用从2开始的循环，将所有可以被2整除的数字标记为false。然后，我们继续用相同的方式遍历数组，将可以被3整除的数字标记为false。依次类推，直到遍历完整个数组。在这个过程中，我们只需要遍历到根号n即可。

最后，我们可以遍历该数组，输出所有标记为true的数字，即为100以内的素数。

以下是C++代码实现：


#include<iostream>
#include<cmath>
using namespace std;
int main()
{
  bool is_prime[101] = { true };
  is_prime[0] = false;
  is_prime[1] = false;
  for (int i = 2; i <= sqrt(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 << " ";
    
  }
  cout << endl;
  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

可以看到，使用C++实现100以内素数筛选法非常简单。对于更大的范围，我们也可以使用相同的思路进行优化。

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

下一篇: C++字符串输入方法

评论区

()

相似文章