21xrx.com
2024-12-23 01:09:09 Monday
登录
文章检索 我的文章 写文章
C++如何寻找素数?
2023-07-06 19:31:54 深夜i     --     --
C++ 寻找 素数

C++是一种高级编程语言,它可以通过编写程序来寻找素数。素数是只能被1和本身整除的正整数。在算法和数据结构中,寻找素数是一个重要的问题。下面我们来看看如何用C++来寻找素数。

1.暴力枚举法

暴力枚举法是最简单的方法。它从2到N-1枚举每一个数字,判断是否能整除它。如果不能整除,那么就是素数。这个算法的时间复杂度是O(N)。下面是代码实现:

#include

using namespace std;

bool isPrime(int n){

  for(int i=2;i

    if(n%i==0)

      return false;//不能被整除

  }

  return true;//是素数

}

int main(){

  int n;//输入数字

  cin>>n;

  if(isPrime(n))

    cout< <<"是素数"<

  else

    cout< <<"不是素数"<

  return 0;

}

2.优化算法

暴力枚举法的时间复杂度是O(N),但是我们可以对它进行优化。我们不需要枚举到N-1,只需要枚举到sqrt(N)就可以了。因为如果一个数字不能被sqrt(N)整除,那么它也不能被N整除。下面是代码实现:

#include

#include

using namespace std;

bool isPrime(int n){

  int m=sqrt(n);

  for(int i=2;i<=m;i++){//最大到sqrt(N)

    if(n%i==0)

      return false;//不能被整除

  }

  return true;//是素数

}

int main(){

  int n;//输入数字

  cin>>n;

  if(isPrime(n))

    cout< <<"是素数"<

  else

    cout< <<"不是素数"<

  return 0;

}

3.筛法

筛法是一种高效的算法。它能够在O(NloglogN)的时间复杂度内得到小于等于N的所有素数。下面是代码实现:

#include

#include //memset需要这个头文件

using namespace std;

const int MAXN=10000001;//最大范围

bool prime[MAXN];

void getPrime(){

  memset(prime,true,sizeof(prime));//初始化

  prime[0]=false;

  prime[1]=false;

  for(int i=2;i*i<=MAXN;i++){

    if(prime[i]){

      for(int j=i*i;j<=MAXN;j+=i){//筛去合数

        prime[j]=false;

      }

    }

  }

}

int main(){

  int n;//输入数字

  cin>>n;

  getPrime();//计算素数表

  if(prime[n])

    cout< <<"是素数"<

  else

    cout< <<"不是素数"<

  return 0;

}

以上就是几种常见的寻找素数的方法,学好C++,自然对其进行更深一步的理解。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复