21xrx.com
2025-03-22 17:56:51 Saturday
文章检索 我的文章 写文章
C++程序：输出第n小质数
2023-07-04 19:52:53 深夜i     15     0
C++ 程序 输出 第n小 质数

质数是指除了1和它本身之外，没有其他的因数能够整除这个数的自然数。求一个数列中第n小的质数是一个经典的问题，对程序员来说也是一项不可避免的任务。下面介绍使用C++来输出第n小的质数的方法。

首先，我们需要明确一个质数的定义和判断方法。一个数是质数，当且仅当它是大于1的自然数，且它不能被它本身以外的数整除。因此，我们可以写一个函数来判断一个数是否为质数，这个函数的代码如下:

bool isPrime(int n) {
  if (n <= 1)
    return false;
  
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0)
      return false;
    
  }
  return true;
}

这个函数采用了“试除法”的方法，通过从2到n平方根之间的所有数去试除n，来判断是否为质数。如果在这个范围内，有能整除n的数，那么n就不是质数，返回false；否则，n就是质数，返回true。

接下来，我们需要写一个函数来输出第n小的质数。这个函数通过遍历所有自然数，统计出质数的数量，来求得第n小的质数。代码如下:

int nthPrime(int n) {
  int cnt = 0;
  for (int i = 2;; ++i) {
    if (isPrime(i)) {
      ++cnt;
      if (cnt == n)
        return i;
      
    }
  }
  return -1;
}

这个函数通过调用刚才的“isPrime”函数来判断一个数是否为质数，如果是质数，则计数器“cnt”+1，当计数器达到n时，返回当前遍历到的这个数i。

最后，我们在main函数中调用“nthPrime”函数并输出结果，代码如下:

#include <iostream>
using namespace std;
int nthPrime(int n) {
  int cnt = 0;
  for (int i = 2;; ++i) {
    if (isPrime(i)) {
      ++cnt;
      if (cnt == n)
        return i;
      
    }
  }
  return -1;
}
int main() {
  int n;
  cout << "请输入正整数n：";
  cin >> n;
  cout << "第" << n << "小的质数是：" << nthPrime(n) << endl;
  return 0;
}

这个程序需要用户输入一个正整数n，然后输出第n小的质数。

经过上面的介绍，相信你已经知道如何使用C++来输出第n小的质数了。通过判断一个数是否为质数，统计已经找到的质数数量，即可找到第n小的质数。这是一个简单而又经典的算法题，也是提高程序员的编程能力和算法思维的好方法。

  
  

评论区