21xrx.com
2025-03-22 03:09:26 Saturday
文章检索 我的文章 写文章
求解c++中100以内的素数
2023-06-23 05:34:40 深夜i     --     --
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的素数，则需要使用其他更优秀的算法来求解。

  
  

评论区