在 C++ 中檢查一個數字是否為質數
Jinku Hu
2023年10月12日
本文將介紹幾種方法在 C++ 中檢查數字是否為質數。
在 C++ 中使用試除法檢查數字是否為質數
質數測試是確定給定數字是否為質數的演算法名稱。檢查數字是否為質數的簡單解決方案是將自然數從一個數字迭代到給定的數字，並檢查除法是否沒有餘數。
一些見解可以改進此方法。第一個-所有整數 n 的除數小於或等於 n/2，這意味著搜尋空間已減小。在下面的示例中，我們還實現了一個 validateInput 函式，以從使用者那裡獲取整數並驗證該整數是否已成功儲存在相應的變數中。該程式在無限迴圈中執行，不斷向使用者詢問該號碼，然後將訊息列印到 cout 流中。
#include <algorithm>
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;
bool isPrime(unsigned long long &n) {
if (n <= 1) return false;
for (uint i = 2; i < n; ++i)
if (n % i == 0) return false;
return true;
}
template <typename T>
T &validateInput(T &val) {
while (true) {
cout << "Enter the natural number: ";
if (cin >> val) {
break;
} else {
if (cin.eof()) exit(EXIT_SUCCESS);
cout << "Enter a valid natural number!\n";
cin.clear();
cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
int main() {
unsigned long long num;
while (true) {
validateInput(num);
isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
}
exit(EXIT_SUCCESS);
}
C++ 中使用相對優化的方法來檢查數字是否為質數
我們可以通過僅測試小於或等於 n 的平方根的除數來繼續優化先前的方法，這對所有自然數都成立。請注意，所有大於 3 的質數都可以表示為 6k+-1 的形式，其中 k 是大於零的整數。它進一步意味著，有效的方法恰好是測試 2 和 3 的數值可除性。如果先前的條件沒有消除給定的數字不是質數，則應測試所有形式為 6k+-1 的數字，該數字也應小於 n 的平方根。請注意，例如當終端中斷被捕獲時（比如Ctrl+D），validateInput 從 while 迴圈中斷。
#include <algorithm>
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;
template <typename T>
T &validateInput(T &val) {
while (true) {
cout << "Enter the natural number: ";
if (cin >> val) {
break;
} else {
if (cin.eof()) exit(EXIT_SUCCESS);
cout << "Enter a valid natural number!\n";
cin.clear();
cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
bool isPrime(unsigned long long &n) {
if (n <= 3) return n > 1;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6)
if (n % i == 0 || n % (i + 2) == 0) return false;
return true;
}
int main() {
unsigned long long num;
while (true) {
validateInput(num);
isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
}
exit(EXIT_SUCCESS);
}
作者： Jinku Hu
