C++语言求素数方法 |21xrx.com

C++语言求素数方法

2023-07-08 10:26:01 深夜i -- --

C++ 素数求解方法

C++语言是一种常见的编程语言，它可以用来编写各种各样的程序，包括求素数的算法。求素数是数学研究中的一个重要问题，也有很多实际应用。下面介绍几种C++语言求素数的方法。

方法一：暴力枚举法

暴力枚举法是最基本的一种求素数的方法。所谓暴力枚举，就是从2开始，对每个数都试除一次，如果能被整除就不是素数。程序实现就是一个嵌套循环，时间复杂度为O(n^2)。

代码实现：


#include <iostream>
using namespace std;
bool isPrime(int n){
  for(int i=2; i<n; i++){
    if(n%i == 0)
      return false;
    
  }
  return true;
}
int main(){
  int n;
  cout<<"请输入一个正整数："<<endl;
  cin>>n;
  if(isPrime(n))
    cout<<n<<"是素数"<<endl;
  
  else
    cout<<n<<"不是素数"<<endl;
  
  return 0;
}

方法二：优化暴力枚举法

上面的暴力枚举法虽然简单易懂，但是时间复杂度比较高，效率不高。我们可以对它进行优化，减少不必要的试除次数。具体实现方法就是从2到sqrt(n)进行试除，如果找到一个因子，另一个因子就是n/i，这样可以减少一半的试除次数。时间复杂度为O(sqrt(n))。

代码实现：


#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n){
  int sqroot = sqrt(n);
  for(int i=2; i<=sqroot; i++){
    if(n%i == 0)
      return false;
    
  }
  return true;
}
int main(){
  int n;
  cout<<"请输入一个正整数："<<endl;
  cin>>n;
  if(isPrime(n))
    cout<<n<<"是素数"<<endl;
  
  else
    cout<<n<<"不是素数"<<endl;
  
  return 0;
}

方法三：筛法

除了暴力枚举法，还有一种经典的求素数方法——筛法。筛法的核心思想是先将2~n的数都标记为素数，然后从2开始依次遍历每个数，如果它没有被标记为素数，就说明它是一个质数，然后将它的倍数都标记为合数。这样遍历完后，标记为素数的数就是所有的素数。时间复杂度为O(nloglogn)。

代码实现：


#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000000;
bool isPrime[MAXN+1];
void sieve(int n){
  memset(isPrime, true, sizeof(isPrime));
  isPrime[0] = isPrime[1] = false;
  for(int i=2; i*i<=n; i++){
    if(isPrime[i]){
      for(int j=i*i; j<=n; j+=i){
        isPrime[j] = false;
      }
    }
  }
}
int main(){
  int n;
  cout<<"请输入一个正整数："<<endl;
  cin>>n;
  sieve(n);
  if(isPrime[n])
    cout<<n<<"是素数"<<endl;
  
  else
    cout<<n<<"不是素数"<<endl;
  
  return 0;
}

总结：

以上就是C++语言求素数的几种常见方法，其中暴力枚举法和优化暴力枚举法比较简单易懂，但是效率不高；筛法效率较高，但是实现稍微有点复杂。具体使用是否需要根据实际需求来选择，以达到更好的效果。

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

下一篇: C++中的逻辑运算符：与、或、非

评论区

()

相似文章