エラトステネスの篩について。

Question

エラトステネスの篩で、7から始まる素数表というのは、あるのでしょうか？教室に電卓の第一巻に、
素数表には、7から始まっていました。30年以上前の本を借りてきたので、わかる方は少ないとはおもいますが、分かる方がいましたら、ご教授下さい。

stomachman · Accepted Answer

No.8へのコメントについてです。

> ①2,3,5は別に作っておく。とはどういうことでしょうか？

知らんす。「別に作」るだなんて意味のはっきりしないことを言ってるのは、誰？

> ②7から数えて5つ目の素数はなぜ、19ではないのでしょうか？9個を登録とはどういうことでしょうか？ご教授下さい。

7から数えて5つ目の素数は19ですよね。No.8の

> 5より大きい素数について「小さい順に何番目の素数までをリストに入れるか」をあらかじめ

というところと、

> すると、7から数えて5つ目の素数は17なので、289(=17^2)以下のnについてならば、それが素数かどうかを調べることができるわけです。

という記述はチョンボでした。p[1]=5ですから、正しくはそれぞれ

5以上の素数について「小さい順に何番目の素数までをリストに入れるか」をあらかじめ

すると、5から数えて5つ目の素数は17なので、289(=17^2)以下のnについてならば、それが素数かどうかを調べることができるわけです。

です。

ありものがたり · Answer

←No.10
ごめん、それたぶん私。 No.4 に書いた。
写真の文章は、私にとってはあまり違和感がない。
たぶん、この著者は私がそういう本を読んでた頃に
そういう本を書いてた世代の人で、要するに相当の御高齢。
コンピューターと言えば、専門家以外はNECのPCで
BASICを使ってた時代の文献だと思う。考古学やね。

stomachman · Answer

> 拡大した写真を以下のURLに

そんなことより、回答を読んで理解する努力をなされば良いのにな。

stomachman · Answer

No.7へのコメントについて。
　最初のご質問の趣旨と全然違っちゃってますが、ま、付き合うか。

[1] nが素数かどうかを判定するのに、素数を小さい順に並べたリストpを使って、p[1], p[2], …の順に割り切れるかどうかをテストするわけです。このとき、√n よりも大きい素数で割り算してみる必要はない。
　例えば n=77が素数かどうかを調べるには（√n = 8.77なので) p[s]≦8であるような素数だけで割ってみれば良いんです。77÷11は割り切れますけれども、11で割ってみる必要はない。なぜならその答は77÷11=7であり、商は11より小さい。そしてこれはもうすでにすでに77÷7のテストで割り切れることが分かっているからです。なので、√n＜p（つまりn/p＜p）であるpで割り切れるかどうかをテストする必要はない。pが小さい順にテストをしていくからこそ、こういうことが言えるんですね。…と、まずはここまでを理解なさった上で。

> ①3°で、n／ps≦psならnを出力(素数)、n/ps＞psとなったらやめる。とは

[2] このアルゴリズムは（ボケてて見えんのですが、おそらく）5より大きい素数について「小さい順に何番目の素数までをリストに入れるか」をあらかじめ指定しておくようになっているのでしょう。だから、nが素数だとわかってnをプリントしても、すでに見つかった素数がリストに入れるべき予定の個数に達していたら、素数のリストpにnを登録しない。（これによってメモリを節約する。）
　一方、素数を小さい順に並べたリストがp[1]～p[s]までしかないとき、これらを使って「nが素数かどうか」を判定できるのはn≦p[s]^2 （つまり n/p[s]≦p[s]）の場合に限られます。それより大きいnについては判定ができない。だからプログラムは終了です。これが「n/p[s]＞p[s] （つまりn＞p[s]^2 ）になったらやめる」ということですね。

> ②後、6°続きで、ある電卓で記憶装置を8個( 1個はループを制御するためのインデックス-レジスタ)を使い、l＝5したがって5,7,11,13,17の9個を登録してのところがわかりません。

[3]（ボケてて見えんので、何言ってんだかわからんですが、おそらく）[2]で説明した「小さい順に何番目の素数までをリストに入れるか」の指定がlなのでしょう。l=5だというのなら「リストに入れるのは5個だけ」と決めてある。すると、7から数えて5つ目の素数は17なので、289(=17^2)以下のnについてならば、それが素数かどうかを調べることができるわけです。

>③最後の文の、piによる商がpi以下になったら打ち切るという判定もなぜ加える必要があるのでしょうか？

[4]（これまた、ボケてて見えんので何言ってんだかわからんですが、おそらく）このアルゴリズムは、nが素数かどうかを判定するのに、リストpにある素数全部について割り切れるかどうかのテストをやっているんではないでしょうかね。そうだとすると無駄な計算をやっていて効率が悪い。
　割り切れるかどうかをn/p[1], n/p[2], …と試して行って、もしどこかで割り切れたら、それ以上試し続けなくたって「nは素数でない」と判定できます。これは当たり前ですね。
　しかし[1]で説明した通り、nが素数かどうかを知るためには、√n よりも大きい素数で割り算してみる必要はない。だから、割り切れるかどうかをn/p[1], n/p[2], …と試して行って、どれでも割り切れないままついにn/p[i]≦p[i]（つまりn≦p[i]^2 すなわち √n ≦ p[i] ）になったら、それ以上試し続けなくたって、nは素数だと判定できる。このことを「piによる商（つまり n/p[i]）がpi以下（つまりn/p[i]≦p[i]）になったら打ち切る」と言っているんでしょう。

stomachman · Answer

No.5へのコメントについて。

> この3行の解説を

n:= n+2
　　if flag then n:= n+2
　　flag := NOT(flag)

という手続きは、flagが真だと
　　n:=n+2
　　n:=n+2
　　flag := 偽
という動作をします。これによって、nは4増えた。そして、次にこの部分を実行する時にはflagが偽になっていますから、
　　n:=n+2
　　flag := 真
という動作をします。これによって、nは2増えた。そして、次にこの部分を実行する時にはflagが真になっています。

アンドロメダシティ · Answer

画像は小さすぎて読む気はしないが、要は「エラストテネスの篩」の、もっと効率的なプログラミングについて興味を持ったということか。車輪配列を使う方法があるけど、車輪配列とベルトラン・チェビシェフの定理が関係あることをどこかで見たのかな。

stomachman · Answer

No.3 に追記。余計なお世話ですけど：

ボケてて読めないのを心眼で読みますと、このページに書いてあるアルゴリズムは、「エラトステネスの篩」をそのままやってるんじゃありません。むしろ「いかにメモリをケチるか」という話をしているんです。

小さい順に素数を並べた表p[1], p[2], ...を作っていく。そのために、p[1]=5とし、n を 7, 11, 13, 17, 19, …と増やしていく（つまり5より大きい((2×3)の倍数)±1を小さい順に発生していく）過程で、「nは素数かどうか（すなわち、nが素数p[1], p[2], ... （ただしp[m]>n/p[m]になったら終わり)のどれでも割り切れないかどうか）」をテストし、素数だとわかったら表pにnを追加し、ついでにnをプリントする。
　ここで、p[m]>n/p[m]をテストするためには、最初に表pがカラッポでは困る。なので、あらかじめp[1]=5が入れてある。そんなわけで、初めてプリントされるのは7ってことになります。
　なお、「nを11, 13, 17, 19,  …と増や」すということを、フラグを使って
　　n:= n+2
　　if flag then n:= n+2
　　flag := NOT(flag)
とやっている。つまり「nを4増やしたら次は2増やして、nを2増やしたら次は4増やす」ってことです。

ところで、30年以上前の本だということですけど、いや30年前でもすでにこれ、かなり古臭い書きようですね。40年前より「ふるい」感じです。

ありものがたり · Answer

7 からは珍しいかなあ。
ＰＣ でやるときに、表のメモリー容量を減らすために
最初から 2 と 3 の倍数は除いておいて
表のマスを割り当てない... というのは、よく行われるけど。
5 の倍数まで除外しとくのは、初めて聞いたかと思う。
除外する素数の個数をあまり増やすと、
表へのアクセスが不規則になって
そこで時間の無駄が発生するから。

stomachman · Answer

「素数2と素数3の倍数は最初から除外し、さらに5が素数であることを使って、以下の計算をやる」（だから、この手順で最初に見つかる素数は7。）ということが、左のページの中程に丁寧に説明してある。

アンドロメダシティ · Answer

> エラトステネスの篩で、7から始まる素数表というのは、あるのでしょうか？
　相変わらず意味不明な日本語だなwwwwwwwww
　エラトステネスの篩は自然数から素数を拾い出すアルゴリズムだが、それと
　　　「7から始まる素数表」
なるものと何か特別な関係でもあるのかwwwwwwwww

! エラトステネスの篩（十進BASIC）
LET n = 100
DIM s(n)
MAT s = ZER　! 配列 s の全要素に 0(zero) を代入 ※s = 0 ではダメ
LET k = 0
FOR i = 2 TO n
　 IF s(i) = 0 THEN
　　　PRINT USING "####":i;
　　　LET k = k + 1
　　　IF MOD(k,10) = 0 THEN
　　　　 PRINT
　　　END IF
　　　FOR　j = i^2 TO N STEP i
　　　　 LET s(j) = 1
　　　NEXT j 
　 END IF
NEXT i

END

n = 100の実行結果
　 2　 3　 5　 7　11　13　17　19　23　29
　31　37　41　43　47　53　59　61　67　71
　73　79　83　89　97

7からの素数を表示したかったら
　　　IF i > 5 THEN PRINT USING "####":i;
　　　IF i > 5 THEN LET k = k + 1
とすればよいwwwwwwwww

7　11　13　17　19　23　29　31　37　41
　43　47　53　59　61　67　71　73　79　83
　89　97

あ～、早朝からバカバカしいwwwwwwwwwwwww

エラトステネスの篩について。

No.8へのコメントについてです。

←No.10

> 拡大した写真を以下のURLに

No.7へのコメントについて。

No.5へのコメントについて。

画像は小さすぎて読む気はしないが、要は「エラストテネスの篩」の、もっと効率的なプログラミングについて興味を持ったということか。

No.3 に追記。

7 からは珍しいかなあ。

「素数2と素数3の倍数は最初から除外し、さらに5が素数であることを使って、以下の計算をやる」（だから、この手順で最初に見つかる素数は7。

> エラトステネスの篩で、7から始まる素数表というのは、あるのでしょうか？

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング