给定数字 n，寻找小于 n 的最接近的素数 C++

给定一个数字 n，我们需要找到小于 n 的最接近的素数。如果从 n - 1 开始检查，我们可以很容易地找到这个数字。我们来看一些例子。

输入

10

输出

7

算法

  • 初始化数字 n。
  • 编写一个从 n - 1 到 1 的循环
    • 返回你找到的第一个素数
  • 如果你没有找到任何小于给定 n 的素数，则返回 -1

实现

以下是上述算法在 C++ 中的实现

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
   if (n == 2) {
      return true;
   }
   for (int i = 2; i <= ceil(sqrt(n)); i++) {
      if (n % i == 0) {
         return false;
      }
   }
   return true;
}
int getNearestPrimeNumber(int n) {
   for (int i = n - 1; i > 1; i--) {
      if (isPrime(i)) {
         return i;
      }
   }
   return -1;
}
int main() {
   int n = 20;
   cout << getNearestPrimeNumber(n) << endl;
   return 0;
}

输出

如果你运行以上代码，你会得到以下结果。

19

更新于: 23-Oct-2021

1K+ 浏览量

开启你的 职业生涯

完成课程，获得认证

开始
广告