stdinから正の整数Nを読み取り、Nが素数であるかどうかを調べようとしています。
Nをsqrt(N)までのすべての正の数に除算できることはわかっていますが、これには時間がかかり、アルゴリズムでは時々誤検知が発生するため、これを解決するためのヒューリスティックを探しています。
昨年、コラージュで数値を選択し、Nがその数値(またはその因数)で割り切れるかどうかを確認するアルゴリズムについて学びました。そうでない場合は、Nが素数であると判断できますが、誤って識別されます。素数として約1/40の時間。
誰かが私が話しているこのアルゴリズムを認識していますか?それへのリンクは非常に役に立ちます。