21xrx.com
2025-03-16 14:41:45 Sunday
文章检索 我的文章 写文章
C++实现筛法求100以内素数
2023-06-25 15:23:11 深夜i     13     0
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++,用它来实现更多有用的算法。

  
  
下一篇: 如何卸载Node.js

评论区

请求出错了