![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
No.4ベストアンサー
- 回答日時:
単純な説明を,素数q以下の素数を2つを用いて作られる最大の数は
q^2となります.因子の数を増やすと,素因子自体は小さくなりますので,
つまり整数Nに含まれる最大の素因子pは
√(N)≧pとなります.
よろしいでしょうか.
No.2
- 回答日時:
「事足りる」という言い方が、微妙ですね。
試し割り法を行うとき、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
- 回答日時:
こういうのは,数学的証明云々より,自分で『納得する』ことが重要です.そして,『納得する』ために効果的なのは,自分で手を動かすことです.
「エラトステネスのふるい」という古典的な「素数の探し方」があります.M以下の素数を探したければ,2からMまでの自然数をすべて書き並べておいて,まず2に○印をつけて2の倍数を全部×印で消す,次に3に○印をつけて3の倍数を消す,…というぐあいに,合成数を除去していきます.
(M以下の整数Nを「試し割りで素因数分解する」というのは,この作業をして「どこかの段階でNが×印で消されるか,それともNが最後まで残るか」を確かめるのと同じことです.)
これを,たとえば M=100 で,実際に紙と鉛筆で手を動かしてやってみることを勧めます.
自分でやってみると,だんだんわかってきます.
2の倍数,3の倍数,5の倍数まで作業を終えて,次に7の倍数を消す段階で,新たに×印をつける最小の数は何でしょう?
また,この作業をどこまでやれば「できあがり」(合成数を除去し尽くした状態)に達するでしょうか? (言い換えれば,ある段階を過ぎると「新たに×印をつけるべき数」がなくなりますが,それはどの段階でしょうか?)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 整数問題 11 素数再びの再び 36 2023/04/29 14:59
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 「素数」とは、「1と、それ自身でしか割り切れない数」。 「素因数分解」も「素数」の仲間ですか? 3 2022/04/14 22:45
- 数学 方程式 √x=-1 の解 2 2022/07/08 17:26
- 数学 【 数A 自然数の積と素因数の個数 】 2 2023/03/02 23:58
- 数学 x^p-1=(x-1)(x-ζ)(x-ζ^2)・・・(x-ζ^p-1)と複素数の中で因数分解できる理 1 2022/11/23 14:59
- 数学 これまでに愚かな回答者を何人も見てきました。 それでも私は問うてみたい。 京都大学の入試問題に 「 6 2023/05/01 14:06
- 小学校 約数の調べ方。 小学生の子供に分かりやすいように説明したいです。 例えば素因数分解するとします。2が 4 2022/08/24 15:14
- 数学 数学 因数分解 高校などで習う因数分解では、 次数の最も低い文字に着目すると、 簡単に解ける場合があ 2 2022/08/02 22:55
- 数学 素因数分解は素数になったら辞めるはずなのに、 画像のようにルート24の素因数分解が2の2乗×6と、 5 2023/06/13 22:57
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
おねがいします!!!!!
-
よって・ゆえに・したがって・∴...
-
3,4,7,8を使って10を作る
-
数学の「証明」のときなどの接...
-
元夫が彼女の存在を隠す理由
-
数学の証明問題で、「証明終了」...
-
証明終了の記号。
-
一様連続 e^x 証明
-
Zn=Z/nZのすべてのイデアルにつ...
-
liman=a(n→∞)、limbn=b(n→∞)な...
-
無理数って二乗しても有理数に...
-
親の再婚相手との問題です。私...
-
幽霊が存在していないことを証...
-
大学の給付型奨学金について 現...
-
あみだくじ
-
極限に関する証明について
-
「証明証」と「証明書」はどう...
-
巡回群と巡回群の直積は巡回群?
-
3の倍数であることの証明
-
分かる方教えてください。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
素数の積に1を加算すると素数で...
-
証明終了の記号。
-
数学の証明問題で、「証明終了」...
-
数学の「証明」のときなどの接...
-
3,4,7,8を使って10を作る
-
幽霊が存在していないことを証...
-
「証明証」と「証明書」はどう...
-
rankに関する証明問題です。
-
よって・ゆえに・したがって・∴...
-
一様連続の証明
-
素数の性質
-
中3数学 2つの続いた整数では、...
-
(4^n)-1が3の倍数であることの...
-
スカラー場とベクトル場
-
なぜ独身だと養子が持てないの...
-
夫が亡くなった後の義理家族と...
-
無理数って二乗しても有理数に...
-
婿養子に入ったのに出て行けと...
-
兄弟の子どもの養子縁組は可能...
-
一様連続 e^x 証明
おすすめ情報