C++如何输入n并求第n小的质数？ |21xrx.com

C++如何输入n并求第n小的质数？

2023-07-05 07:37:59 深夜i -- --

C++ 输入 n 第n小质数

在编写程序时，有时需要找到一定范围内的质数或者找到第n小的质数。C++作为一种强大的编程语言，提供了丰富的数学计算和算法处理功能。下面，我们来探讨如何用C++输入n并求第n小的质数。

要实现这个功能，我们可以采用两种方法：一种是暴力枚举法，另一种是筛法。暴力枚举法是指遍历一个范围内的所有数，通过判断每个数是否为质数来求出第n小的质数；而筛法则是通过预先筛选出一定范围内的质数，再从中选取第n小的质数。

首先，我们来看暴力枚举法。在这种方法中，我们可以利用循环遍历一个范围内的数，判断每个数是否为质数。具体的代码如下所示：


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

在上述代码中，我们首先定义了一个函数isPrime(num)，用来判断一个数是否为质数。该函数中，我们先判断num是否小于等于1，如果是，则返回false；然后从2开始遍历到num - 1，如果发现num%i==0，则说明num不是质数，直接返回false。最后，如果遍历完成后没有找到num的因子，则说明num是质数，返回true。

在主函数中，我们先输入n的值，然后从2开始遍历每个数，遇到一个质数就将计数器count增加1。当count等于n时，输出当前数i即为第n小的质数。

然而，这种方法效率较低，适用于较小的数。对于大量数据的情况，我们需要使用更高效的筛法。

其中，比较常用的一种筛法是“埃氏筛法”，即每次筛选出一个质数p，将能够整除p的数从序列中删除，以减少后续的质数计算次数。在筛法中，我们需要预先定义一个数组保存所有可能的质数，然后再进行筛选。具体的代码如下所示：


#include<iostream>
using namespace std;
const int MAXN = 1000000;  // 定义数组的最大长度
bool isPrime[MAXN+1];    // 定义数组，保存所有可能的质数
int prime[MAXN+1];     // 定义数组，保存筛选后的质数
void PrimeSect() {
  memset(isPrime, true, sizeof(isPrime));   // 初值为true
  int num = 0;
  for (int i = 2; i <= MAXN; i++) {
    if (isPrime[i]) {
      prime[++num] = i;    // 新加一个质素
      for (int j = i; j <= MAXN; j += i) {
        isPrime[j] = false;   // 删除不是质数的数
      }
    }
  }
}
int main() {
  int n;
  cout << "请输入n的值: ";
  cin >> n;
  PrimeSect();   // 调用该函数，获得所有可能的质数
  cout << "第" << n << "小的质数是：" << prime[n];
  return 0;
}

以上就是C++输入n并求第n小的质数的两种方法。使用这些算法，我们能够方便地求出一定制定范围内的质数或者找到第n小的质数，以提高程序的效率和准确度。

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

下一篇: 为什么Dev-C++出现“makefile.win”？

评论区

()

相似文章