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

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

2023-07-13 03:10:43 深夜i -- --

C++ 筛法 100 素数

C++是一种高效的编程语言，可以实现许多复杂的算法。其中，求素数是经常使用的算法，在本文中我们将介绍如何使用C++实现筛法求100以内的素数。

筛法是一种较为简单的求素数的方法，它的基本思想是先把要求的素数范围内的自然数都列出来，然后从小到大依次筛选，将不是素数的数去掉。这个方法的时间复杂度为O(n log(log n))，效率比较高。

下面是使用C++实现筛法求100以内素数的代码：


#include<iostream>
using namespace std;
int prime[10001]={0},num=0;  //定义一个素数数组和素数个数
int main()
{
  int i,j;
  //从2到100筛素数
  for(i=2;i<=100;i++)
  {
    if(prime[i]==0)  //如果i是素数
    {
      prime[num++]=i;  //将i添加进素数数组中
      for(j=i*i;j<=100;j+=i)  //将i的倍数全部标记为非素数
      {
        prime[j]=1;
      }
    }
  }
  //输出素数
  for(i=0;i<num;i++)
  {
    cout<<prime[i]<<" ";
  }
  cout<<endl;
  return 0;
}

代码中，我们首先定义了一个素数数组prime和素数个数num，然后从2到100依次筛选素数。对于每个素数i，我们将其添加进素数数组中，并标记其倍数全部为非素数。筛选完毕后，输出素数即可。

使用C++实现筛法求100以内素数，不仅简单易懂，而且效率较高。这个算法可以应用到多种场景中，如判断一个数是否为素数、找出一定范围内的素数等。让我们一起学习和掌握C++，用它来实现更多有用的算法。

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

下一篇: 微软C++软件编译爱心的C语言代码

评论区

()

相似文章