21xrx.com
2025-04-26 08:01:07 Saturday
文章检索 我的文章 写文章
求解c++中100以内的素数
2023-06-23 05:34:40 深夜i     24     0
C++ 素数 100

在C++中，求解100以内的素数可以使用质数筛法来实现。质数筛法是一种比较常见的求素数的算法，其基本思路是从小到大遍历每个自然数，找出它的所有因数，并标记出不是素数的自然数，在遍历到100之后，未被标记的自然数即为100以内的所有素数。

具体的实现可以使用一个布尔类型的数组，假设为is_prime，其中is_prime[i]表示i是否为素数，初始时所有元素均为true。从2开始遍历，对于每个素数p，将p的倍数全部标记为false，直到遍历到100。最后遍历一遍is_prime数组，输出所有值为true的下标即为100以内的所有素数。

以下是C++程序代码实现：

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
  const int MAX_NUM = 100;
  bool is_prime[MAX_NUM + 1];
  for (int i = 2; i <= MAX_NUM; ++i)
  {
    is_prime[i] = true;
  }
  for (int i = 2; i <= sqrt(MAX_NUM); ++i)
  {
    if (is_prime[i])
    {
      for (int j = i * i; j <= MAX_NUM; j += i)
      {
        is_prime[j] = false;
      }
    }
  }
  cout << "100以内的素数有：" << endl;
  for (int i = 2; i <= MAX_NUM; ++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以内的素数的内容，这种方法的时间复杂度是O(n log log n)，效率较高。而对于大于100的素数，则需要使用其他更优秀的算法来求解。

  
  

评论区

请求出错了