今、家にある中学の参考書を読みながら、中学数学を勉強しているものです。その中の素数についての一番最初の問題で、
次のうちから、素数を選べ。
1 6 13 25 51 79 87 91
という問題があり、その解法の一つでエラトステネスのふるいというもの(2から順に自然数を書き、2を残して2の倍数を消し、3を残して3の倍数を消し、5を残して5の倍数を消す、以下同様にして求める…という方法)があるのですが、上の問題でずっとエラトステネスのふるいを使いながら合成数を消していくと、11の倍数を消すところで、「13、79は11で割り切れず、13÷11、79÷11ともに商が11より小さくなるから素数である。」と参考書にあり、そこでふるいをかける作業は終わっています。
この参考書(特に、"13÷11、79÷11ともに商が11より小さくなるから素数である。"というところ)のこの部分と、ずっとにらめっこをしてきたのですが、何故「13÷11、79÷11ともに商が11より小さくなるから素数である」と言い切れるのか、分かりませんでした…。
少なくとも13は、次に11の倍数となる数である11×2=22の間に13が存在しないから素数、と言い切れる感じはするのですが、79だと、たとえ11で割り切れなくても、13、17で割り切れるかもしれない…(もちろん実際そんなことはないのですが)、と、感覚的にそう思ってしまいます。そして、「13÷11、79÷11ともに商が11より小さくなるから素数である」を言いかえれば、「商が11より大きくなる場合は、素数でない可能性がある(121以降の数であれば、たとえ今の時点で11で割り切れなくても、素数でないかもしれない)」というのも、よく分かりません…。
そんなこんなで、このふるいが11で終わっている理由が分からないのです。
馬鹿みたいな問題かもしれないのですが、頭が堅くて、分からなくて困っているので、良かったら教えていただければ嬉しいです…。
No.4ベストアンサー
- 回答日時:
エラトステネスのふるい自体について説明をしておきます.
エラトステネスのふるいは,まず,1を消して2を残して2の倍数を消します.次に
(1)残っている最小の数を残してその数の倍数を消す.
この(1)を繰り返す,という素数を求める方法です.
これだと無限に繰り返さなければなりませんね.
たとえば,121までの素数を求める場合どのようにするかということを考えて見ましょう.(問題に合わせて121にしていますので,これはいくらでもいいのですが)121=11×11ですね.これより小さい数が素数でない場合,約数がどのようになるかが分かればいいわけです.(実際にはこの約数は11(:求めたい範囲の平方根)よりも小さいことになるのですが・・・)
121以下の整数が素因数分解できたとします.そのとき因数がp,qの二つであったとすると,p,qのいずれかは11よりも小さくなります.なぜなら両方とも11より大きければ,その数は,121より大きくなってしまいます.
∴p<11orq<11
つまり,121より小さい合成数(素数でないものをこういいます.)は必ず,11以下の因数を持っている.つまり,11以下の約数になるということです.逆に11までの約数を持たなければ,その数(121以下)が素数ということになります.
これを一般の場合にすると求める数の平方根を超えない最大の素数まで確認すれば,いいことを示すこともできるはずです.(この辺はご自身でどうぞ)
ようやく分かりました…!商のことを考えるには、素数にならない数のことを考えればよかったんですね。
私のような相手に、どうも有難うございました。
No.3
- 回答日時:
No.1です。
そーですね、今回も分かりやすく「221の場合」を考えてみましょう。
221を11で割ると、「商=20、余り=1」となり一見素数のように思えます。
しかし実際には「13でわると商=17、余り=0となる」ので「素数ではない」のです。
こーゆーのがあるから「素数ではないかもしれない」ということになります。
しかしこれはあくまで「11で割った商が11より大きい数(=11×11=121より大きい数)の場合」です。
問題に出ている数を見てみると「すべて121以下です」ので、そのような数を考える必要はありません。
だから「11まで考えればいい」ことになります。
この回答への補足
本当にごめんなさい…まだ分からないです。
何故、11で割った商が11より大きい数(121以上)の場合は商を考える必要があるのかということと、問題になっている数は121以下だから、11までしか考えなくていいということ…何故そう言いきっていいのかが分からないんです。
言い換えれば、なんで13や79は11の倍数でないから、これ以上考えなくても良いのかが分からないんです。確かに下の方の回答の方法(平方根の大小で考える方法)で考えると納得できるのですが、商が11より大きい・小さいで考える方法ですと、やっぱり納得ができないんです…。
No.2
- 回答日時:
素数を調べる場合、平方根までを調べればいいのです。
仮に、ある数が素数でないとすれば、なにかの数の積として表すことができます。
数をxとすると、
x = a × b
となりますね。
この場合、aかbのどちらかはxの平方根以下で、
どちらかは平方根以上になります。
「両方ともxの平方根未満」ということはあり得ません。
だって、そうしたら、掛けてもxにはなりませんので。
(同様に、「両方ともxの平方根より大きい」ということもありません。)
だから、2から始めて、数の平方根まで調べて約数がなければ、素数としていいのです。
(細かいことですが、上の議論で「以上」「以下」「未満」「より大きい」には注意してください)
問題の場合、最大の数が100未満です。
だから、平方根は、最大でも10未満です。
だからこの場合、本当は10以下の素数(最大の素数は7)に
ついて調べればいいのですが、
念のため11まで調べたのでしょう。
No.1
- 回答日時:
分かりやすく、「26の場合」を考えてみましょうか。
26は確かに「11では割り切れないが、13では割り切れる」数です。
が、13で割った時の商は2ですので、「2の倍数を消すときにすでに消されています」。
他の13で割り切れる数も同様です。(17、19でも)
したがって、「既に消されているので考える必要がない」ということです。
「11より大きい場合~」というのはこの逆で「まだ消されていないけども13や17、19をした時に消されてしまう(=素数ではなくなる)かもしれない」という理由からです。
この回答への補足
rmz1002さん、早速のご回答どうもありがとうございます。
「26の場合」の話までは理解出来たのですが、「11より大きい場合~」の話は、やっぱり「商が11より大きい場合」、ということで話されてるのでしょうか…。だとしたら本当にごめんなさい、そこがまだ、よく分からないです…(バカですみません…)。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 命題 nが合成数ならば、√n以下の素数pが存在し、pはnを割り切る の対偶を考える際、nが合成数なら 1 2023/05/23 00:24
- 数学 nは正の整数であり、偶数。 n(n+1)(n+2)(n+3)は素因数が3つ。 nを求めよ。 という問 8 2022/09/26 18:15
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
- その他(教育・科学・学問) 小学生の算数の商について 3 2023/03/06 14:11
- 数学 教えてください。 2 2022/06/30 14:26
- Ruby 初心者プログラミング 3 2022/10/12 11:31
- 国家公務員・地方公務員 公務員試験の数的処理で苦戦しています。 1 2023/01/30 08:56
- 数学 数学の複素数の証明問題です。 (1)複素数全体の集合に2要素間の実数と同様な大小を定義できないことを 2 2022/08/28 11:17
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
累乗根について
-
数A難しすぎやしませんか…。 ま...
-
数学の数式を小説に書く場合、...
-
2の10乗が1024であることはなぜ...
-
高校受験生です。数学において...
-
数学で1の次数は0と習いました...
-
高1の問題です!!
-
数学の勉強で、進学校の人は講...
-
中学校 3年 数学 平方根を小数...
-
中学 数学 なぜ√625の平方根は±...
-
2nπと数学の教科書にのっていま...
-
下手な先生の授業ではどう勉強...
-
平方根の中がプラスになる理由...
-
"k"の意味
-
数学の感想文
-
【至急】 √10より大きく√30より...
-
平方根
-
「表す」と「表わす」
-
旧課程と新課程のチャート式
-
理系なのに数学が壊滅的です。(...
おすすめ情報