C++编程：输出第n小的质数 |21xrx.com

C++编程：输出第n小的质数

2023-06-26 17:38:34 深夜i 15 0

C++编程输出第n小质数

在C++编程中，找到第n小的质数是一个经典的计算问题。质数是指只能被1和它本身整除的正整数，也称为素数。找到第n小的质数需要考虑多种算法和数据结构。

一种简单的方法是使用最基本的遍历算法，从2开始逐个判断每个大于2的整数是否为质数，直到找到第n个为止。这种算法的时间复杂度为O(n^2)，因此不适用于大规模数据的计算。

更加高效的算法包括埃拉托斯特尼筛法、线性筛法等。其中埃拉托斯特尼筛法是一种经典的筛法，它基于质数的定义，将所有不是质数的数筛除，最终得到所有的质数。线性筛法是在埃氏筛法的基础上进一步优化，使用欧拉定理和莫比乌斯反演等数学工具，可以快速找到第n小的质数。

下面给出一个使用线性筛法的示例代码，可以找到第n小的质数：

#include <iostream>
#include <vector>
using namespace std;
vector<int> primes;    // 存储质数
vector<bool> isPrime(1e6, true); // 标记是否为质数
void sieve(int n) {
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i <= n; ++i) {
    if (isPrime[i]) {
      primes.push_back(i);
    }
    for (int j = 0; j < primes.size() && i*primes[j] <= n; ++j) {
      isPrime[i*primes[j]] = false;
      if (i % primes[j] == 0)
        break;
      
    }
  }
}
int nthPrime(int n) {
  sieve(n*22);
  return primes[n-1];
}
int main(){
  int n = 100;
  cout << "第" << n << "小的质数是：" << nthPrime(n) << endl;
  return 0;
}

在此代码中，sieve函数使用线性筛法筛选出n以内的所有质数，并将其存储在向量primes中。nthPrime函数直接返回第n个质数，调用sieve函数来处理数据。在主函数中，我们设置n=100，输出第100小的质数是1291。

总的来说，找到第n小的质数是一道具有挑战性的计算问题，需要综合运用各种算法和数据结构来实现。以上代码提供了一个可行的方法，在实际应用中可以根据数据规模和时间效率的要求进行选择和优化。

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

下一篇: 如何创建C++工程

评论区

相似文章

C++实现输入n求第n小质数的方法

C++是一种功能强大的编程语言，它可以通过很多种方式实现各种算法。在本文中，我们将介绍一种使用C++来实现输入n求第n小质数的方法。