給定數字 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+ 瀏覽量

開啟你的 職業生涯

完成課程，獲得認證

開始
廣告