C++求解质数问题 |21xrx.com

C++求解质数问题

2023-07-04 20:59:24 深夜i -- --

C++ 求解质数问题

质数，即只能被1和自身整除的正整数，是数学中一个非常重要的概念。在计算机算法中，求解质数问题也是一个经典的问题。C++是一种高效的编程语言，在求解质数问题上也有很好的表现。

首先，我们需要明确一下质数的定义和判断方法。判断一个数是否是质数可以采用试除法，即用2到其平方根之间的正整数逐一试除，如果发现能被整除的数，则说明该数不是质数。如果到达平方根时仍未发现能被整除的数，则说明该数是质数。

下面是用C++实现求解质数问题的代码。


#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
  if(n<2) return false;
  for(int i=2;i*i<=n;i++){
    if(n%i==0) return false;
  }
  return true;
}
int main(){
  int n;
  cin>>n;
  for(int i=2;i<=n;i++){
    if(isPrime(i)) cout<<i<<" ";
  }
  return 0;
}

以上代码中定义了一个 `isPrime` 函数用于判断是否是质数。在主函数中，从2到n逐一判断，如果是质数则输出。

除了上述代码，也可以使用筛法求出质数。具体来说，从2开始标记每个质数的倍数，最后未被标记的即为质数。下面是基于筛法的代码。


#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000000;
bool p[MAXN+5];
void getPrime(int n){
  memset(p,0,sizeof(p));
  for(int i=2;i<=n;i++){
    if(!p[i]){
      cout<<i<<" ";
      for(int j=i*i;j<=n;j+=i){
        p[j]=true;
      }
    }
  }
}
int main(){
  int n;
  cin>>n;
  getPrime(n);
  return 0;
}

以上代码中定义了一个 `getPrime` 函数用于求出n以内的质数，具体的实现使用了筛法思想。在主函数中，调用该函数即可求解。需要注意的是，由于数组开不下MAXN大小，需要使用动态开辟数组或者需要时再开辟数组的方法。

总之，C++是一个非常适合求解质数问题的编程语言。无论是采用试除法还是筛法，都可以使用C++进行高效的实现。因此，对于学习C++的程序员而言，研究求解质数问题是非常重要的。

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

下一篇: 学完Java后学Python会更快吗？

评论区

()

相似文章