平方根を用いた素因数分解

質問

ある整数Nを試し割りで素因数分解するとき
√N>p
を満たす最大の素数pまで試し割りすれば事足りる
というものがありますが、この数学的証明はどうなるのでしょうか

回答No.4

masudaya · ベストアンサー

単純な説明を,素数q以下の素数を2つを用いて作られる最大の数は
q^2となります.因子の数を増やすと,素因子自体は小さくなりますので,
つまり整数Nに含まれる最大の素因子pは
√（N)≧pとなります.

よろしいでしょうか.

回答No.6

178-tall

諸賢のコメントに、N = p^2 の場合を勘案すれば、

　「√N≧p を満たす素数 p で N を整除できるものが存在しなければ、N は素数」

なのかな？

回答No.5

alice_44

←A NO.4　なりません。
例えば N = 26 のとき、
最大の素因子は p = 13 ですが、
13 = p > √N ≒ 5.0990… です。

回答No.3

alice_44

訂正：

試し割り法を行うとき、N の約数 x が見つかれば、
N を N/x で置き換えて、試し割りの続きをします。

回答No.2

alice_44

「事足りる」という言い方が、微妙ですね。

試し割り法を行うとき、N の約数 x が見つかれば、
N を N/x で置き換えて、再度最初から試し割りをします。
そして、更新した N が素数と判定できたところで
作業を終了するのです。

だから、
N の約数 x が、在るとすれば x ≦ √N の範囲に在る
ということが保証されれば、試し割りする除数は
x ≦ √N の範囲で「事足りる」ことになります。

全ての素因数を、試し割りした除数の中から出したい
というのであれば、x ≦ √N ではなく、
x ≦ N/2 までやらなくてはダメです。

N の約数 x が、在るとすれば x ≦ √N の範囲に在る
ことの証明ですが…

自然数 N, x, y について、
N = xy のとき x ≦ √N または y ≦ √N です。
もし x > √N かつ y > √N であれば、
xy > N になってしまいますから。(背理法)

試す除数が素数だけでよいのは、
N が x で割りきれないことが既に判っていれば、
N は x の倍数では割りきれないからです。
試し割りは、小さい除数から順に試してゆきますからね。

回答No.1

boiseweb

こういうのは，数学的証明云々より，自分で『納得する』ことが重要です．そして，『納得する』ために効果的なのは，自分で手を動かすことです．

「エラトステネスのふるい」という古典的な「素数の探し方」があります．M以下の素数を探したければ，2からMまでの自然数をすべて書き並べておいて，まず2に○印をつけて2の倍数を全部×印で消す，次に3に○印をつけて3の倍数を消す，…というぐあいに，合成数を除去していきます．
（M以下の整数Nを「試し割りで素因数分解する」というのは，この作業をして「どこかの段階でNが×印で消されるか，それともNが最後まで残るか」を確かめるのと同じことです．）

これを，たとえば M=100 で，実際に紙と鉛筆で手を動かしてやってみることを勧めます．
自分でやってみると，だんだんわかってきます．
2の倍数，3の倍数，5の倍数まで作業を終えて，次に7の倍数を消す段階で，新たに×印をつける最小の数は何でしょう？
また，この作業をどこまでやれば「できあがり」（合成数を除去し尽くした状態）に達するでしょうか？ （言い換えれば，ある段階を過ぎると「新たに×印をつけるべき数」がなくなりますが，それはどの段階でしょうか？）