素数表について。

以下の画像の7から始まる素数表がありますが、プログラミング(BASIC言語)で作られているのですが、画像の解説をお願いできないでしょうか？すみませんが。

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

• 

  ①はなぜあなたはそう思ったのでしょうか？ご教授下さい。すみませんが。

  No.7の回答に寄せられた補足コメントです。 補足日時：2021/01/19 19:43

• 

  5, 7, 11, 13, 17の5個までが登録されるようにして。というように考えるとどうなるのでしょうか？
  ご教授下さい。すみませんが。

  No.17の回答に寄せられた補足コメントです。 補足日時：2021/01/22 16:56

• 

  ＃14の54行で、フラグを立てるのは分かるのですが、この場合のフラグは何なのでしょうか？ご教授下さい。すみませんが。

  No.22の回答に寄せられた補足コメントです。 補足日時：2021/01/22 22:57

• 

  同じく＃14のプログラミングの所です。

  No.26の回答に寄せられた補足コメントです。 補足日時：2021/01/23 09:47

• 

  すみません。
  ここです。
  5行目の間違いだと思うのですが。
  Link: http://codepad.org/Oxfd5gz9

  No.34の回答に寄せられた補足コメントです。 補足日時：2021/01/26 03:58

No.30 ベストアンサー 回答者： cametan_42 回答日時： 2021/01/24 15:13

> P∧2 で、超えるもので、(P＋ 2)∧2 ー 1になるのが、なぜ、− 1をするのでしょうか？

これ、おかしな話なんで無視して構わないと思うんですけどねぇ。
適当な素数Pを持ってきて、P + 2が素数だなんて保証はないでしょう。
この本の文面、

> 実際、Pの次の素数Qに対して、Q^2 - 1まで、したがって(P + 2)^2まで進めて構いません。

とか書いてるけど、「したがって」もクソも

・常にQ = P + 2である

なんて保証は当然ありません。

P = 17の時、Q = 19 = P + 2

は成り立つけど、

P = 13の時、P + 2 = 15 => 素数ではない(Qは17である)

あるいは、

P = 19の時、P + 2 = 21 => 素数ではない(Qは23である)

と成り立たないですからね。
あくまでlが5で登録された最後の素数が17だから成り立ってる。全然一般論じゃない。何考えてこんな「如何にも一般論」的な記述してんだかサッパリ分かりません。
だから言ってるでしょ?悪書です。
こんな「おかしな余談」は忘れて構わない。
(そして「悪書」の記述につきあわされているこちらの身にもなってもらいたい)

いずれにせよ、「探索範囲」で考えると、ある素数Qがあったとして、Q^2は当然Qで割り切れるのでQ^2は素数ではないのが明らかです。
そうすると、素数じゃない数はどーでも良いんで、素数の候補としてはそれより1個手前の数までQより小さい素数での探索範囲とする、と言う考え方です。
詳しい話はWikipediaを参考にすること。

試し割り法:
https://ja.wikipedia.org/wiki/%E8%A9%A6%E3%81%97 …

この回答へのお礼

P∧2 はなぜ出てきたのでしょうか？すみません。これが最後の質問にします。
ご教授下さい。すみません。

お礼日時：2021/01/24 15:44

No.39 回答者： tknakamuri 回答日時： 2021/01/27 08:52

>LinkのpのURLでなぜ、29行目と括弧されているのかが分かりません。

何を言っているのか
全然解らんです。

No.38 回答者： tknakamuri 回答日時： 2021/01/27 07:59

>s＝5が初めて出てきた時点で、もう素数の登録数は、

>満杯だから、5行目でいいのではと思ったのです。
>それ以降、s＝5は変わりませんから。ご教授下さい。

最初に解っている素数は5のみで、Sはpに登録した
素数の数なので 最初はs=1
7が発見されるとsは2に
11が発見されるとsは3に
13が発見されるとsは4に
17が発見されるとsは5に
増え、これで満杯です。

で、「5行目でいい」とは？
全く意味不明です。

この回答へのお礼

Link: http://codepad.org/Oxfd5gz9
では、以下のURLの29行目とはどういうことでしょうか？
s を表示するよう付け加えて実行してみました（29行目）。

C code - 58 lines - codepad

確かに 5 より大きくはならないようです。

s が L と等しくなった時点で f1 が 1 になり、s に加算する部分が実行されなくなるためでしょう。
LinkのpのURLでなぜ、29行目と括弧されているのかが分かりません。
ご教授下さい。5行目でいいというのは、out put の所で、s＝5になっているからです。ご教授下さい。すみませんが。

お礼日時：2021/01/27 08:04

No.37 回答者： tknakamuri 回答日時： 2021/01/26 23:21

>s＝5だけなら、5行目でいいと思うのですが？なぜ、

>29行目を指した意味がわかりません。

何の話なんだか
全然わかんないです。

「5行目でいい」って何がどういいのでしょう？

この回答へのお礼

s＝5が初めて出てきた時点で、もう素数の登録数は、満杯だから、5行目でいいのではと思ったのです。それ以降、s＝5は変わりませんから。ご教授下さい。

お礼日時：2021/01/26 23:24

No.36 回答者： tknakamuri 回答日時： 2021/01/26 16:35

>なぜ、29行目なのでしょうか？ご教授下さい。

すみませんが

29行目は素数と判断できた数とその時の
sを表示しているだけですが
「なぜ」の全体が見えないですね。

この回答へのお礼

s＝5だけなら、5行目でいいと思うのですが？なぜ、29行目を指した意味がわかりません。ご教授下さい。すみませんが。

お礼日時：2021/01/26 18:06

No.35 回答者： tknakamuri 回答日時： 2021/01/26 10:19

>すみません。

>ここです。
>5行目の間違いだと思うのですが。
>Link: http://codepad.org/Oxfd5gz9

5行目は int main( void ) {
だと思いますが・・・

素数が発見されると素数を登録するこのコード

if ( f1 == 1 ) { /* 算法4。35行まで。 */
goto label60;
}
else { /* 算法5。43行まで。 */
s = s + 1;
p[ s ] = n;
if ( s == L ) {
f1 = 1;
}
}

ｓ=Lでf1 が立つともはや素数は p に登録されないのは
一目瞭然だと思います。

余談ですが、BASICのコードの移植とはいえ
メインループが goto で組んであってその中に
普通の for ループがあるのはなかなかシュール(^^;

ループ制御が弱いBASICで goto が多用されるのは
仕方ないですが、さすが C で goto 多用で
スパゲッティされるとくらっと来ます(^^;

この回答へのお礼

なぜ、29行目なのでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/26 14:10

No.34 回答者： tknakamuri 回答日時： 2021/01/26 00:34

>sが6以上になることはないということでしょうか？

ですね。s=l になるとF1が1になって
それ以上増えなくなるようになってます。

この回答へのお礼

では、以下のURLの29行目とはどういうことでしょうか？
s を表示するよう付け加えて実行してみました（29行目）。

C code - 58 lines - codepad

確かに 5 より大きくはならないようです。

s が L と等しくなった時点で f1 が 1 になり、s に加算する部分が実行されなくなるためでしょう。

お礼日時：2021/01/26 03:53

No.33 回答者： tknakamuri 回答日時： 2021/01/25 21:04

大体全部いり。

4 ms でした(Ryzen5 3400G, python3.8)。
①候補を 6で割って1,5 余る数にする
②候補÷素数<=素数 となる素数でのみで判定

あんまり速くならないのは、pythonのリストが遅いからだと
思う。

この回答へのお礼

すみません。以下の質問に答えていただけますでしょうか？
＃14のプログラムで、sが6以上になることはないということでしょうか？
l＝5なので。ご教授下さい。すみませんが。

お礼日時：2021/01/25 21:14

No.32 回答者： cametan_42 回答日時： 2021/01/24 17:54

> 確かに試し割り法では、(P［i＋ 1］)∧2 未満であることが成り立ちますが、

> (P［i ］)∧2 未満であるとは言っていない

本当にそうですか?
今、P[i]は分かってる、として、じゃあP[i+1]は今この時点で分かってるんですか?
逆じゃないですか?P[i+1]を知りたいのに、どうやって上限(P［i＋ 1］)∧2を先に知るんでしょうか?

Wikipediaの記述、

> 最も運が悪い場合でも、P[i+1]^2>nを満たすPiまで確かめれば良い。また、Piまで試すことでP[i+1]^2未満のnまでの判定が可能である。

ってのはそういう意味ですよ。

よく読んで下さい。

No.31 回答者： cametan_42 回答日時： 2021/01/24 15:51

> P∧2 はなぜ出てきたのでしょうか？

本も悪書だけど、貴方もダメな人ですねぇ。
Wikipediaの「試し割り法」のリンク貼ったでしょ?読みましたか?
読んでないのに質問してるんですか?
ふざけてます?

この回答へのお礼

確かに試し割り法では、(P［i＋ 1］)∧2 未満であることが成り立ちますが、
(P［i ］)∧2 未満であるとは言っていないので、17∧2 ＝289としたという解釈で大丈夫でしょうか？意味不明ですみません。ご教授下さい。

お礼日時：2021/01/24 16:22