中小企業の働き方改革をサポート>>

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

このQ&Aに関連する最新のQ&A

平方根」に関するQ&A: 平方根

A 回答 (6件)

単純な説明を,素数q以下の素数を2つを用いて作られる最大の数は


q^2となります.因子の数を増やすと,素因子自体は小さくなりますので,
つまり整数Nに含まれる最大の素因子pは
√(N)≧pとなります.

よろしいでしょうか.
    • good
    • 0

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



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

なのかな?
   
    • good
    • 0

←A NO.4 なりません。


例えば N = 26 のとき、
最大の素因子は p = 13 ですが、
13 = p > √N ≒ 5.0990… です。
    • good
    • 1

訂正:



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

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



試し割り法を行うとき、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 の倍数では割りきれないからです。
試し割りは、小さい除数から順に試してゆきますからね。
    • good
    • 0

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



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

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

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


人気Q&Aランキング

おすすめ情報