C++如何输出N个素数 |21xrx.com

C++如何输出N个素数

2023-07-06 08:53:25 深夜i -- --

C++ 输出素数数量N

C++是一种广泛应用于编程领域的高性能编程语言。在C++中，如何输出N个素数呢？本文将介绍几种关于输出N个素数的方法。

方法一：暴力枚举法

暴力枚举法是一种常见的求解素数的方法，它的思路是通过循环遍历一定范围内的所有整数，对于每一个整数，判断其是否为素数，如果是，则记录下来。

具体实现如下：


#include <iostream>
#include <vector>
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;
}
vector<int> getPrime(int N) {
  vector<int> primes;
  int num = 2;
  while (primes.size() < N) {
    if (isPrime(num)) {
      primes.push_back(num);
    }
    num++;
  }
  return primes;
}
int main() {
  int N = 10;
  vector<int> primes = getPrime(N);
  for (auto p : primes)
    cout << p << " ";
  
  cout << endl;
  return 0;
}

方法二：埃氏筛法

埃氏筛法是另一种求素数的方法，它的思路是首先把2到N的所有整数标记为素数，然后从2开始，不断地把素数的倍数标记为合数，直到筛完为止。

具体实现如下：


#include <iostream>
#include <vector>
using namespace std;
vector<int> getPrime(int N) {
  vector<int> primes;
  vector<bool> isPrime(N + 1, true);
  for (int i = 2; i <= N; i++) {
    if (isPrime[i]) {
      primes.push_back(i);
      for (int j = i * i; j <= N; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return primes;
}
int main() {
  int N = 10;
  vector<int> primes = getPrime(N);
  for (auto p : primes)
    cout << p << " ";
  
  cout << endl;
  return 0;
}

上述两个方法都能输出N个素数，但是它们的时间复杂度不同。暴力枚举法的时间复杂度为O(N^2)或者O(NlogN)，而埃氏筛法的时间复杂度为O(NloglogN)。

总之，以上便是关于输出N个素数的两种方法，根据实际情况进行选择即可。

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

下一篇: 如何在Qt中使用QML连接C++信号

评论区

()

相似文章