C++实现输入n求第n小质数的方法 |21xrx.com

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

2023-06-23 18:07:37 深夜i -- --

C++ 输入 n 第n小质数

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

质数是指大于1的自然数中，除了1和该数本身以外，没有其他因数的数。求第n小的质数，可以采用以下方法：

1.定义变量n，表示要求的第n小的质数。

2.从2开始循环遍历自然数，直到找到第n个质数为止。

3.在循环中，通过判断每个自然数是否为质数，来确定它是否是第n小的质数。

4.如果找到了第n小的质数，输出该质数即可。

下面是使用C++代码实现这个方法的示例：


#include <iostream>
using namespace std;
bool isPrime(int num) {
  if (num == 1)
    return false;
  for (int i = 2; i * i <= num; i++) {
    if (num % i == 0)
      return false;
  }
  return true;
}
int main() {
  int n;
  cout << "请输入n：" << endl;
  cin >> n;
  int count = 0;
  int i = 2;
  while (count < n) {
    if (isPrime(i))
      count++;
    i++;
  }
  cout << "第" << n << "小的质数是：" << i - 1 << endl;
  return 0;
}

在这个示例中，我们定义了一个函数isPrime，用于判断一个自然数是否为质数。然后，在主函数中，我们首先输入要求的第n小的质数，然后使用一个while循环，从2开始不断遍历自然数，判断每个自然数是否为质数，直到找到第n个质数为止。最后，输出找到的第n小质数的值。

优化：

显然，上述算法的时间复杂度较高，如果输入较大的n，程序的运行时间将较长。下面对其进行优化：

1.在isPrime函数中，可以将循环范围设为i的平方根，因为如果i有因数，则它有必然小于i的因数，且必有一个小于等于其平方根。

2.在while循环中，可以将i设为3的倍数，减少循环数量。

提醒：题目要求给出的数一定不能到5e6开始怎样优化？可以大量优化，筛选出1000以内的素数，再用这些素数筛选出剩余范围的素数。

以下是优化后的C++代码示例：


#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int num) {
  if (num == 1)
    return false;
  for (int i = 2; i * i <= num; i++) {
    if (num % i == 0)
      return false;
  }
  return true;
}
int main() {
  int n;
  cout << "请输入n：" << endl;
  cin >> n;
  int count = 1;
  int i = 3;
  int j = 2;
  while (count < n) {
    if (isPrime(i)) {
      count++;
      j = i;
    }
    i += 2;
  }
  cout << "第" << n << "小的质数是：" << j << endl;
  return 0;
}

总之，使用C++实现输入n求第n小的质数的算法，可以高效地实现此类问题的求解，我们可以根据具体情况选择不同的优化方法以提高程序效率。

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

下一篇: VC++6.0 中的字体是什么？

评论区

()

相似文章