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

C++使用筛选法求解100以内的素数

2023-06-29 05:06:21 深夜i -- --

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

C++是一种高性能的编程语言，可以用来解决各种复杂的数学问题，比如求解素数。素数是指只能被1和自身整除的自然数，在数学中具有重要的意义。在这篇文章中，我们将介绍如何使用C++编写筛选法来求解100以内的素数。

筛选法是一种比较简单的求解素数的方法，其思路是从2开始，将每个素数的倍数标记为合数，最终剩下的数就是素数。使用C++编写筛选法求解100以内的素数的代码如下：


#include <iostream>
using namespace std;
int main() {
  bool prime[100];
  for(int i=0;i<100;i++) {
   prime[i]=true;
  }
  for(int p=2;p*p<100;p++){
   if(prime[p]==true){
     for(int i=p*p;i<100;i+=p){
      prime[i]=false;
     }
   }
  }
  for(int p=2;p<100;p++){
   if(prime[p]==true)
     cout<<p<<" ";
   
  }
  return 0;
}

在上面的代码中，我们首先定义了一个bool数组prime来表示100以内的数是否为素数。我们将数组中的值都初始化为true。接着，我们从2开始循环，找到第一个素数2，并将2的所有倍数标记为合数。然后，我们找到下一个素数3，将3的所有倍数标记为合数。以此类推，直到我们找到的素数的平方大于100为止。最后，我们再次循环数组，输出所有标记为素数的数，即1到100之间的所有素数。

使用筛选法求解100以内的素数是非常高效的，时间复杂度只有O(n*loglogn)，而且可以方便地扩展到任意范围的素数求解。因此，对于需要求解大量素数的问题，筛选法是一种非常好的选择。

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

下一篇: C++ 如何遍历文件夹？

评论区

()

相似文章