projectpn
projectpn
最も基本的なアルゴリズムで、\scriptstyle{\lfloor \sqrt n \rfloor}までの数でひとつひとつ割り切れるかどうかを判定していく。
入力:素数判定する数 n
出力:nが素数であれば「nは素数である」、合成数であれば「nは合成数である」と出力する。
ステップ1
\scriptstyle{2 \sim \lfloor \sqrt n \rfloor}までkを変化させ、kがnを割り切れば「nは合成数である」と出力して終了する。
ステップ2
上記のkの全てでkがnを割り切れなかったとき、「nは素数である」と出力して終了する。

kを\scriptstyle{n}まででなく\scriptstyle{\lfloor \sqrt n \rfloor}まで変化されればよいことの証明
nが合成数のとき、nが\scriptstyle{\sqrt n}以下の素因数を持つことを示せばよい。
\scriptstyle{n=p\times q}(p,qは2以上の自然数)
というように少なくとも2数の積に分解できる。pもqも\scriptstyle{\sqrt n}より大きいと仮定すると、\scriptstyle{n>p\times q}となってしまい\scriptstyle{n=p\times q}に反する。したがって、pかqのどちらかは\scriptstyle{\sqrt n}以下であるから、nは\scriptstyle{\sqrt n}以下の素因数を持つ。(証明終)

「試し割り法」をウィキ内検索
最終更新：2012年06月30日 14:28