C++求质数的算法详解 |21xrx.com

C++求质数的算法详解

2023-06-23 14:33:53 深夜i -- --

C++ 质数算法详解

质数是指只能被1和自身整除的自然数，求质数是计算机程序设计中一个经典的问题。C++作为高效且常用的编程语言之一，其求质数的算法也非常常见。本文将详细介绍C++中求质数的算法。

1. 试除法算法

试除法算法是最简单的一种求质数的方法，其思路是将待验证的数从2到该数的平方根-1进行遍历，判断该数是否能被整除。如果其中有一个数能够整除该数，则该数不是质数；反之，则该数是质数。

C++中的示例代码实现如下：


#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n){
  if(n <= 1)
    return false;
  for(int i = 2; i <= sqrt(n); i++){
    if(n % i == 0)
      return false;
  }
  return true;
}
int main(){
  int n;
  cin >> n;
  if(is_prime(n))
    cout << "该数是质数" << endl;
  else
    cout << "该数不是质数" << endl;
  return 0;
}

2. 筛法算法

筛法算法是一种更高效的求质数的方法，其思路是从2开始，将小于等于n的数的倍数所在的位置标记为合数。最后所有未标记的位置即为质数。

C++中实现筛法算法有以下两种方法：

（1）埃氏筛法

埃氏筛法是最简单的一种筛法算法，其思路是从2开始将小于等于n的数的倍数所在的位置标记为合数。最后所有未标记的位置即为质数。

C++中的示例代码实现如下：


#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n){
  if(n <= 1)
    return false;
  vector<bool> prime(n + 1, true);
  for(int i = 2; i <= sqrt(n); i++){
    if(!prime[i])
      continue;
    for(int j = i * i; j <= n; j += i){
      prime[j] = false;
    }
  }
  return prime[n];
}
int main(){
  int n;
  cin >> n;
  if(is_prime(n))
    cout << "该数是质数" << endl;
  else
    cout << "该数不是质数" << endl;
  return 0;
}

（2）欧拉筛法

欧拉筛法是一种更高效的筛法算法，其思路是从2开始将小于等于n的数的倍数所在的位置标记为合数，同时优化了标记合数的过程，减少了重复标记的次数。

C++中的示例代码实现如下：


#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n){
  if(n <= 1)
    return false;
  vector<bool> prime(n + 1, true);
  vector<int> p;
  for(int i = 2; i <= n; i++){
    if(prime[i])
      p.push_back(i);
    for(int j = 0; j < p.size() && i * p[j] <= n; j++){
      prime[i * p[j]] = false;
      if(i % p[j] == 0)
        break;
    }
  }
  return prime[n];
}
int main(){
  int n;
  cin >> n;
  if(is_prime(n))
    cout << "该数是质数" << endl;
  else
    cout << "该数不是质数" << endl;
  return 0;
}

以上就是C++求质数的算法详解，通过以上的介绍可以看出，C++中有多种方法来求质数，需要根据具体的需求选择不同的算法。同时也需要注意算法的时间复杂度和空间复杂度，针对不同的应用场景进行选择。

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

下一篇: C++实现简单的心形代码

评论区

()

相似文章