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

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

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

• 

  なぜ、P∧2 ＝289以下となっているのでしょうか？ご教授下さい。すみませんが。

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

• 

  なぜ、(29行目)を指したのでしょうか？ご教授下さい。すみませんが。わざわざ29行目を指した理由は、なんでしょうか？s＝5と関係しているということでしょうか？ご教授下さい。すみませんが。

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

• 

  メインルーチンとサブルーチンの例をご教示願います。すみませんが。

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

• 

  具体例をお願いしたいです。ご教授下さい。すみませんが。

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

No.6 回答者： mtrajcp 回答日時： 2021/01/26 06:12

5ﾟで

s←s+1
の後に
s=5が限界l=5に達したら,F1=1をセット

…

4ﾟで

F1=1がセットされているならば,

5ﾟ(s←s+1)の処理を行わないで

6ﾟへ飛ぶので

sは6以上にはなりません

この回答へのお礼

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

C code - 58 lines - codepad

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

s が L と等しくなった時点で f1 が 1 になり、s に加算する部分が実行されなくなるためでしょう。
で、Link: http://codepad.org/Oxfd5gz9
で、なぜ29行目なのでしょうか？ご教授下さい。すみませんが。

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

No.5 回答者： mtrajcp 回答日時： 2021/01/25 20:57

Pは素数で

QはPの次の素数だから
P<Q
だから
P^2<Q^2
だから
P^2≦Q^2-1
↓P<P^2だから
∴
P<P^2≦Q^2-1

この回答へのお礼

すみませんが。sが6以上にはならないですよね？l＝5であるので。ご教授下さい。

お礼日時：2021/01/25 22:43

No.4 回答者： mtrajcp 回答日時： 2021/01/25 19:37

「

もっとも上限がNなら,√Nまでのpだけで使えば十分
です
」
と書いてある通り

P=√N
ならば

P^2=Nが上限になります

だけれども

素数Pの次の素数をQとする
P<n≦Q^2-1
となる自然数
nが
合成数ならばnはP以下の素数で割り切れる
nがP以下の素数で割り切れない場合はnは素数である
と言っているのです
だから

P<P^2≦Q^2-1
だから

P^2=Nを超えても
Q^2-1
までなら
素数の判定ができるといっているのです

この回答へのお礼

P＜P∧2 ≦Q∧2 ー 1がなぜ成り立つのでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/25 20:22

No.3 回答者： mtrajcp 回答日時： 2021/01/25 19:02

「

P^2 を超えたというもの
」
とどこにそんな事がかかれているのでしょうか?
意味不明?

画像不鮮明解読不可能で
どこにもそんな事は見当たりません

この回答へのお礼

これで見やすくなったでしょうか？以下のURLです。ご教授下さい。すみませんが。
https://6900.teacup.com/cgu135/bbs/953

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

No.2 回答者： mtrajcp 回答日時： 2021/01/25 16:16

素数Pの次の素数をQとする

P<n≦Q^2-1
となる自然数
nが
合成数ならばnはP以下の素数で割り切れる
nがP以下の素数で割り切れない場合はnは素数である
と言っているのです

nが合成数ならば
n=ab
となる自然数a≧2,b≧2がある
aもbもP以下の素数で割り切れないと仮定すると
a>P
b>P
となりPの次の素数はQだから
a≧Q
b≧Q
だから
n=ab≧Q^2
となってn≦Q^2-1に矛盾するから
nはP以下の素数で割り切れる

だから
nがP以下の素数で割り切れない場合はnは素数である

P=17の時次の素数Q=19だからP=Q+2にしているのです

P=13の時Q=17でQ^2=17^2=289だから
P=13<n≦Q^2-1=289-1となる自然数nで
素数2,3,5,7,11,13で割り切れないものが素数となるのです

この回答へのお礼

P∧2 を超えたというものというのは、どういうことでしょうか？なぜ、P∧2
を考えたのでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/25 16:34

No.1 回答者： t_fumiaki 回答日時： 2021/01/24 13:14

P＋ 2＝QよりP=Q-2

(P＋2)²-1へ代入すると、=(Q-2+2)²-1=Q²-1

中学レベルの数学。

この回答へのお礼

なぜ、− 1をするのでしょうか？ご教授下さい。すみませんが。

お礼日時：2021/01/24 13:28