１から１００までの

質問

１から１００までの素数をもとめるとき、ルート１００（つまり１０）の約数の倍数を消していけばよい。とありましたが、どうしてルート１００なのでしょうか。
例えば１００００までの素数を求めたいとき同じようにルート１００００の約数の倍数を消していけばよいのでしょうか。１５０までの素数を求めたいとき同じようにルート１５０の約数の倍数を消していけばよいのでしょうか。

回答No.5

kmee

> ルート１００（つまり１０）の約数の倍数を消していけばよい

これはちょっと違いますね。
このやりかただと

1～25までの素数
→ √25 = 5 の約数の倍数
→ 1,5 の倍数
1の倍数: 1～25は全て1の倍数→ 全て素数ではない : 事実と反する
5の倍数: 5,10,25以外は素数→ 4は素数では無い: 事実と反する

と、素数を求めることはできません。
ルート１００（つまり１０）の約数の倍数
ではなく
ルート１００（つまり１０）以下の素数の倍数
です。

これは エラトステネスのふるい と呼ばれる手法です。
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

自然数kが素数ではない、というのは
k=a × b (a,bは1より大きい整数)
と表現できる、ということです。
ここで、乗算の交換法則から、 a≦b としても一般性は失われません。
このときのaの最大になるのは、a=bの時です。
k=a^2
a=√k
が最大値です。

回答No.4

masa072

質問文がおかしいですが、修正してお話しします。
１から１００までの素数を求めるには、√100、つまり10までの素数の倍数を消していけばいいです。
即ち、2,3,5,7の倍数を自身を残して消していけばいいです。（１は素数ではないので消し忘れないように）
なぜそれでいいかといえば、例えば39=3×13のように、39は3の倍数でも13の倍数でもありますが、3の倍数で消されますよね。同じく77=7×11も7の倍数の段階で消されます。素因数分解したときの一番小さい素数で消去されてしまいます。その一番小さい整数は√100=10以下であるはずです。（2つとも√100より大きければその結果は100を超えてしまいますね）
一般にa以下の素数を求めるときは、√a以下の素数の倍数を消していけばいいです。

詳しくはエラトステネスのふるいで調べてみましょう。
もしくはプログラムの課題でしょうかね。よくある初心者向けの課題ですね。

回答No.3

umigamitaiyo

正確にはルート１００＝１０までの素数の倍数を消していくです。
↓分かりやすい動画(NHK教育2355：月～金の23:55～0:00でたまに放送される)
http://www.youtube.com/watch?v=GOFgVK_LAKY

　なぜ10までの素数の倍数を消すだけで良いかというと、仮に11を考えると100÷11<10だから、11の倍数はすでにふるい落とされて、13～100までのあいだに存在しない。それ以上の素数についても同様。

回答No.2

notnot

100までの合成数を順に消していくわけですが、100までの合成数の約数の少なくとも１つはルート100以下です。だって、ルート100以上の数を二つ掛けると100以上になっちゃいますから。

従って、後半はその通りです。

回答No.1

山田 太郎（@testman199）

>ルート１００（つまり１０）の約数の倍数を消していけばよい。
だめでしょ。
この方法じゃ９が消えない