algorithm - 数の素数

Question

数値「n」が素数かどうかを確認するには、n の平方根より小さい因数があるかどうかを確認するだけでよいことが知られています。

私の質問は、n の平方根より小さいすべての素数をチェックするだけで十分ではないということです。

Answer 1

次のように主張できます。

チェックする数を とするn。k <= sqrt(n)を割る数があるとするn。さて、k次のように書くことができます。

k = (p_1^a_1)(p_2^a_2)...(p_x^a_x)

ここで、はおよびp_1, p_2, ..., p_xより小さいか等しい素数です。ここで、が を割っており、 が を割っていることがわかっているので、推移性によって、 が を割っていると推測できます。したがって、 が非素数であることを証明するには、素数のいずれかが割り切れるかどうかを確認するだけで十分です。ka_1, a_2, ..., a_x >= 1knp_1, p_2, ..., p_xkp_1, p_2, ..., p_xnn<= sqrt(n)n

Answer 2

はい、係数未満のsqrt（n）を確認するだけで済みます。しかし、このアルゴリズムは少し遅いです。Miller_Rabin_primality という別のより優れたアルゴリズムがあります以前のプロジェクト コード ソース コード

ウィキはこちら