2

stdinから正の整数Nを読み取り、Nが素数であるかどうかを調べようとしています。

Nをsqrt(N)までのすべての正の数に除算できることはわかっていますが、これには時間がかかり、アルゴリズムでは時々誤検知が発生するため、これを解決するためのヒューリスティックを探しています。

昨年、コラージュで数値を選択し、Nがその数値(またはその因数)で割り切れるかどうかを確認するアルゴリズムについて学びました。そうでない場合は、Nが素数であると判断できますが、誤って識別されます。素数として約1/40の時間。

誰かが私が話しているこのアルゴリズムを認識していますか?それへのリンクは非常に役に立ちます。

4

1 に答える 1

4

まあ、いくつかの確率的アルゴリズムがあり、ウィキペディアのページで説明されているものもありますが、ミラー・ラビン・ フェルマーの素数性テストについて話している可能性が最も高いです

2002 年以降、数値が素数であるかどうかを判断する O(log(n)^6) 決定論的アプローチが実際にあることに注意してください - AKS (その開発者にちなんで)と呼ばれます1


これは興味深い問題です。素数性テストは、入力のサイズの多項式 (つまり、対数n) と決定論の両方で行うことはできないと多くの人が考えていましたが、彼らのアプローチはそうではありませんでした。

于 2012-12-12T07:06:33.990 に答える