C++ 中大于 N 的第 K 个质数


在本教程中,我们将编写一个程序,找出大于给定数字 n 的第 k 个质数。

  • 初始化数字 n。
  • 找出所有小于 1000000 的质数,并将它们存储在一个布尔数组中。
  • 编写一个从 n + 1 到 1000000 循环的循环。
    • 如果当前数字是质数,则 k 减 1。
    • 如果 k 等于零,则返回 i。
  • 返回 -1。

示例

我们来看一下代码。

 在线演示

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1e6;
bool prime[MAX_SIZE + 1];
void findAllPrimes() {
   memset(prime, true, sizeof(prime));
   for (int p = 2; p * p <= MAX_SIZE; p++) {
      if (prime[p]) {
         for (int i = p * p; i <= MAX_SIZE; i += p) {
            prime[i] = false;
         }
      }
   }
}
int findKthPrimeGreaterThanN(int n, int k) {
   for (int i = n + 1; i < MAX_SIZE; i++) {
      if (prime[i]) {
         k--;
      }
      if (k == 0) {
         return i;
      }
   }
   return -1;
}
int main() {
   findAllPrimes();
   int n = 5, k = 23;
   cout << findKthPrimeGreaterThanN(n, k) << endl;
   return 0;
}

输出

如果您运行上面的代码,您将得到以下结果。

101

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

如果您在教程中有什么疑问,请在评论区中提出。

更新于:2021 年 04 月 09 日

239 次浏览

职业生涯的最佳开端

完成课程即可获得认证

开始
广告