教えて!gooにおける不適切な投稿への対応について

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

質問者からの補足コメント

  • うーん・・・

    これの画像の解説お願いできますか?

    「エラトステネスの篩について。」の補足画像1
    No.2の回答に寄せられた補足コメントです。 補足日時:2021/01/18 07:35
  • うーん・・・

    拡大した写真を以下のURLに貼ったので、見ていただけると幸いです。
    https://6900.teacup.com/cgu135/bbs/953

    No.7の回答に寄せられた補足コメントです。 補足日時:2021/01/18 21:55
  • うーん・・・

    私のUPした画像で 1°のところに書かれていると思うのですが。ご教授下さい。すみませんが。

    No.10の回答に寄せられた補足コメントです。 補足日時:2021/01/19 16:07
  • うーん・・・

    すみません。なぜ素数Pの次の素数(P+ 2)∧2 ー 1で、P+ 2=Qとして、Q∧ 2ー 1で、なぜ、− 1するのでしょうか?ご教授下さい。すみませんが。なぜ、(P+ 2)∧ 2ー 1はどうやって出てくるのでしょうか?ご教授下さい。すみません。

      補足日時:2021/01/24 10:54
  • うーん・・・

    sが6以上になることもないのでしょうか?l=5の時です。ご教授下さい。すみませんが。

    No.11の回答に寄せられた補足コメントです。 補足日時:2021/01/25 03:10
gooドクター

A 回答 (10件)

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についてならば、それが素数かどうかを調べることができるわけです。


です。
この回答への補足あり
    • good
    • 0
この回答へのお礼

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

お礼日時:2021/01/19 16:06

←No.10


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

では、なぜ、P∧2として求めたのでしょうか?17∧2のことです。後、なぜ、P=17の時しか成り立たないのに、Q∧2 ー 1で、(P+ 2)∧ 2ー 1としたのでしょうか?ご教授下さい。すみませんが。

お礼日時:2021/01/25 02:59

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



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

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])になったら打ち切る」と言っているんでしょう。
    • good
    • 0
この回答へのお礼

すみません。2つほど質問してもよろしいでしょうか?①2,3,5は別に作っておく。とはどういうことでしょうか?②7から数えて5つ目の素数はなぜ、19ではないのでしょうか?9個を登録とはどういうことでしょうか?ご教授下さい。

お礼日時:2021/01/19 15:21

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が真になっています。
この回答への補足あり
    • good
    • 0
この回答へのお礼

すみません。①3°で、n/ps≦psならnを出力(素数)、n/ps>psとなったらやめる。とはどういうことでしょうか?②後、6°続きで、ある電卓で記憶装置を8個( 1個はループを制御するためのインデックス-レジスタ)を使い、l=5したがって5,7,11,13,17の9個を登録してのところがわかりません。それと、③最後の文の、piによる商がpi以下になったら打ち切るという判定もなぜ加える必要があるのでしょうか?
以上3点についてご教授下さい。すみませんが。

お礼日時:2021/01/18 21:29

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

車輪配列を使う方法があるけど、車輪配列とベルトラン・チェビシェフの定理が関係あることをどこかで見たのかな。
    • good
    • 0

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年前より「ふるい」感じです。
    • good
    • 0
この回答へのお礼

n:= n+2
 if flag then n:= n+2
 flag := NOT(flag)
がなぜ、「nを4増やしたら次は2増やして、nを2増やしたら次は4増やす」という意味になるのでしょうか?この3行の解説をご教授下さい。すみませんが。

お礼日時:2021/01/18 15:01

7 からは珍しいかなあ。


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

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

)ということが、左のページの中程に丁寧に説明してある。
    • good
    • 1
この回答へのお礼

なぜ、この手順で、最初に見つかる素数は7なのでしょうか?ご教授下さい。すみませんが。素数5を使って、どうやって7を出したのでしょうか?ご教授下さい。すみませんが。

お礼日時:2021/01/18 14:05

> エラトステネスの篩で、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
この回答への補足あり
    • good
    • 0

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

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング