algorithm - N 対 N/2 の平方根を使用して N が素数であるかどうかを確認する利点は何ですか?

Question

数値が素数であるかどうかを確認するために反復を切り取るのは問題ですか?

元。37 は素数であり、最大 18.5 (37 の半分) と 6.08 (平方根) を比較すると、多くの作業が省略されますが、どちらも同じ原則に従っていますか?

質問してすみません、私は数の平方根を使用してそれが素数であるかどうかを判断するという私の論理を固めようとしており、それを他の人に説明しようとしています

Answer 1

平方根は、大きな数の実行時間を大幅に改善するため、推奨されます。

平方根を制限として使用できるのはなぜですか? N が素数でない場合は、N = p1*p2 として表すことができます。ここで、p1 と p2 の除数は 1 より大きくなります。明らかに、p1 または p2 (または両方) は N の平方根以下です。さらに確認します。

注意として、数値の素数をチェックするより高度な方法が存在します。例: Miller-Rabin primality テスト。このテストは確率的ですが、特定のセットアップでは、最大 64 ビット整数未満のすべての素数に対して正しい答えを生成できます。