C++ で数値が素数かどうかを調べる
胡金庫
2023年10月12日
この記事では、C++ で数が素数であるかどうかを確認する方法のいくつかの方法について説明します。
C++ で試行除算法を使用して数値が素数であるかどうかを確認する
素数性テストは、指定された数が素数であるかどうかを判断するアルゴリズムの名前です。数が素数であるかどうかを確認する簡単な解決策は、自然数を 1 から指定された数まで反復し、除算に余りがないかどうかを確認することです。
いくつかの洞察がこの方法を改善することができます。最初の-整数 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);
}
数値が素数で比較的最適化された方法を使用してあるかどうかを確認する
n の平方根以下の約数のみをテストすることで、以前の方法を引き続き最適化できます。これは、すべての自然数に当てはまります。3 より大きいすべての素数は、6k+-1 の形式で表すことができることに注意してください。ここで、k はゼロより大きい整数です。さらに、効率的な方法は、2 と 3 の値の数の分割可能性をテストすることであることを意味します。前の条件で指定された数が非素数として削除されない場合は、n の平方根よりも小さい 6k+-1 の形式のすべての数をテストする必要があります。validateInput は、ターミナル割り込みがキャッチされると while ループから抜けることに注意してください（例：Ctrl+D）。
#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);
}
著者： 胡金庫
