30n±Pのエラトステネスの篩
2021.02.08　Ver.0.009

2009.11.14　Ver.0.001　新規作成
2009.11.15　Ver.0.002　記事追加
2009.11.16　Ver.0.003　素数表を大きくした
2009.11.21　Ver.0.004　記事追加
2009.12.2　 Ver.0.005 エラトステネスの篩を追加完了
2009.12.13　 Ver.0.006 プログラム追加
2009.12.30　 Ver.0.007 PDF追加
2011. 4130　 Ver.0.008 プログラムバグ修正
2021. 2. 8　 Ver.0.009 プログラムを一本化

まとめのPDF「30n+P形式のエラトステネスの篩」

２、３、５の倍数を除いた素数候補表現は、I=30n+p(1≦p≦29)のとき2x3x5=30の数の中から、

より、 30n+1、30n+7、30n+11,30n+13,30n+17(30n-13),30n+19(30n-11),30n+23(30n-7), 30n+29(30n-1)より、
30n±1、30n±7、30n±11、30n±13となります。

さて、そこで、下の表を作ってみました。
30n±1、30n±7、30n±11、30n±13表

この表より,

49(7x7) +28 77(7x11) +14 91(7x13)　+28 119(7x17) +14 133(7x19) +28 161(7x23) +42 203(7x29) +14 217(7x31) +42 259(7x37)
　　　　　 +28 287(7x41) +14 301(7x43) +28 329(7x47) +14 343(7x49) +28 371(7X53) +42 413(7x59) +14 427(7x61) +42 469(7x67)
　　　　　 +28 497(7x71) +14 511(7x73) +28 539(7x77) +14 553(7x79 )+28 581(7X83) +42 623(7x89) +14 637(7x91) +42 679(7x97)
という繰り返しが見えてきます｡また、
49(11x7) +44 121(11x11) +22 143(11x13) +44 187(11x17) +22 209(11x19) +44 253(11x23) +66 319(11x29) +22 341(11x31) +66 407(11x37)
　　　　　　+44 451(11x41) +22 473(11x43) +44 517(11x47) +22 539(11x49) +44 583(11x53) +66 649(11x59) +22 671(11x61) +66 737(11X67)
という繰り返しが見えてきます｡また、
91(13x7) +52 143(13x11) +26 169(13x13) +52 221(13x17) +26 247(13x19) +52 299(13x23) +78 377(13x29) +26 403(13x31) +78 481(13x37)
　　　　　　+52 533(13x41) +26 559(13x43) +52 611(13x47) +26 637(13x49) +52 689(13x53) +78 767(13x59) +26 793(13x61) +78 871(13x67)
という繰り返しが見えてきます｡また、
119(17x7) +68 187(17x11) +34 221(17x13) +68 289(17x17) +34 323(17x19) +68 391(17x23) +102 493(17x29) +34 527(17x31) +102 629(17x37)
　　　　　　　+68 697(17x41) +34 731(17x43) +68 799(17x47) +34 833(17x49) +68 901(17x53) +102 1003(17x59) +34 1037(17x61) +102 1139(17x67)

このように、素数でないものがある規則の繰り返しで現れるので,まず30n±1、30n±7、30n±11、30n±13表を作って,この繰り返しの規則 にのっとってエラトステネスの篩で削除すれば,もともとの数が少ないので高速化できます｡

たとえば,7の倍数は、以下の表にまとめられます｡

同じことが11,13,17,・・・にも言えます｡
もともと最初の表には30n±1、30n±7、30n±11、30n±13の数しかありませんので,素数でないものは、素数と素数の積ですから
素数でないものは、素数×（30n±1、30n±7、30n±11、30n±13）の数しかありません。

さて、
==================掲示板より================================================
＞2と3と5を除いた素数候補30n±1、30n±7、30n±11、30n±13でも エラトステネスの篩

30k+1=(30m+1)(30n+1)
30k+1=(30m-1)(30n-1)
30k-1=(30m-1)(30n+1)
30k-1=(30m+1)(30n-1)
は何とかなりますが,同様に
30k-7=(30m-1)(30n+7)=30P-7
30k-7=(30m+1)(30n-7)=30P-7
30k+7=(30m+1)(30n+7)=30P+7
30k+7=(30m-1)(30n-7)=30P+7
同じように
30k-11=(30m-1)(30n+11)=30P-11
30k+11=(30m+1)(30n+11)=30P+11
これからあと2組
また
30k-13=(30m-1)(30n+13)=30P-13
30k+13=(30m+1)(30n+13)=30P+13
これからあと2組
また、
30k+1=(30m+7)(30n+13)=30P+91=30(P+3)+1
30K-7=(30m+11)(30n+13)=30P+143=30(P+5)-7
30K-13=(30m+7)(30n+11)=30P+77=30(P+3)-13
これらもあと2組

とやってみるとなんとなくとっかかりが掴めそうな...
==================掲示板より================================================
これですが,よくよく見れば,素数×（30n±1、30n±7、30n±11、30n±13）の数しかありません。

したがって、この規則が全ての30n±1、30n±7、30n±11、30n±13表に含まれる数について成り立つことを証明する必要はありません｡

でも、やっぱり、
「もともと最初の表には30n±1、30n±7、30n±11、30n±13の数しかありませんので,素数でないものは、素数と素数の積ですから
素数でないものは、素数×（30n±1、30n±7、30n±11、30n±13）の数しかありません。」
の証明は必要だな｡

==================掲示板より============================================== ==
要するに,証明は
(30n+p)=(30m+q)(30k+r)
(30n+p)=(30m-q)(30k-r)
(30n-p)=(30m+q)(30k-r)
(30n-p)=(30m-q)(30k+r)
が、p,q,rが1,7,11,13,17,19,23,29のいずれでも成り立つことを示せば良いわけだ｡
4×8×8×8=2048の組合せを全て示せばいいということになる｡
==================掲示板より================================================
ということなので,
1)
(30m+1)(30k+1)=30p+1=(30a-29)(30b-29)
2)
(30m+1)(30k+7)=30p+7=(30a-29)(30b-23)
3)
(30m+1)(30k+11)=30p+11=(30a-29)(30b-19)
4)
(30m+1)(30k+13)=30p+13=(30a-29)(30b-17)
5)
(30m+1)(30k+17)=30p+17=(30a-29)(30b-13)
6)
(30m+1)(30k+19)=30p+19=(30a-29)(30b-11)
7)
(30m+1)(30k+23)=30p+23=(30a-29)(30b-7)　
8)
(30m+1)(30k+29)=30p+29=(30a-29)(30b-1)　


1)
(30m+7)(30k+1)=30p+7=(30a-13)(30b-29)
2)
(30m+7)(30k+7)=30p+49=30(p+1)+19=(30a-13)(30b-23)
3)
(30m+7)(30k+11)=30p+77=30(p+2)+17=(30a-13)(30b-19)
4)
(30m+7)(30k+13)=30p+91=30(p+3)+1=(30a-13)(30b-17)
5)
(30m+7)(30k+17)=30p+119=30(p+3)+29=(30a-13)(30b-13)
6)
(30m+7)(30k+19)=30p+133=30(p+4)+13=(30a-13)(30b-11)
7)
(30m+7)(30k+23)=30p+161=30(p+5)+11=(30a-13)(30b-7)
8)
(30m+7)(30k+29)=30p+203=30(p+6)+23=(30a-13)(30b-1)



1)
(30m+11)(30k+1)=30p+11=(30a-19)(30b-29)
2)
(30m+11)(30k+7)=30p+77=30(p+2)+17=(30a-19)(30b-23)
3)
(30m+11)(30k+11)=30p+121=30(p+4)+1=(30a-19)(30b-19)
4)
(30m+11)(30k+13)=30p+143=30(p+4)+23=(30a-19)(30b-17)
5)
(30m+11)(30k+17)=30p+187=30(p+6)+7=(30a-19)(30b-13)
6)
(30m+11)(30k+19)=30p+209=30(p+6)+29=(30a-19)(30b-11)
7)
(30m+11)(30k+23)=30p+253=30(p+8)+11=(30a-19)(30b-7)
8)
(30m+11)(30k+29)=30p+319=30(p+10)+19=(30a-19)(30b-1)



1)
(30m+13)(30k+1)=30p+13=(30a-17)(30b-29)
2)
(30m+13)(30k+7)=30p+91=30(p+3)+1=(30a-17)(30b-23)
3)
(30m+13)(30k+11)=30p+143=30(p+4)+23=(30a-17)(30b-19)
4)
(30m+13)(30k+13)=30p+169=30(p+5)+19=(30a-17)(30b-17)
5)
(30m+13)(30k+17)=30p+221=30(p+7)+11=(30a-17)(30b-13)
6)
(30m+13)(30k+19)=30p+247=30(p+8)+7=(30a-17)(30b-11)
7)
(30m+13)(30k+23)=30p+299=30(p+9)+29=(30a-17)(30b-7)
8)
(30m+13)(30k+29)=30p+377=30(p+12)+17=(30a-17)(30b-1)



1)
(30m+17)(30k+1)=30p+17=(30a-13)(30b-29)
2)
(30m+17)(30k+7)=30p+119=30(p+6)+29=(30a-13)(30b-23)
3)
(30m+17)(30k+11)=30p+187=30(p+6)+7=(30a-13)(30b-19)
4)
(30m+17)(30k+13)=30p+221=30(p+7)+11=(30a-13)(30b-17)
5)
(30m+17)(30k+17)=30p+289=30(p+9)+19=(30a-13)(30b-13)
6)
(30m+17)(30k+19)=30p+323=30(p+10)+23=(30a-13)(30b-11)
7)
(30m+17)(30k+23)=30p+391=30(p+13)+1=(30a-13)(30b-7)
8)
(30m+17)(30k+29)=30p+493=30(p+16)+13=(30a-13)(30b-1)



1)
(30m+19)(30k+1)=30p+19=(30a-11)(30b-29)
2)
(30m+19)(30k+7)=30p+133=30(p+4)+13=(30a-11)(30b-23)
3)
(30m+19)(30k+11)=30p+209=30(p+6)+29=(30a-11)(30b-19)
4)
(30m+19)(30k+13)=30p+247=30(p+8)+7=(30a-11)(30b-17)
5)
(30m+19)(30k+17)=30p+323=30(p+10)+23=(30a-11)(30b-13)
6)
(30m+19)(30k+19)=30p+361=30(p+12)+1=(30a-11)(30b-11)
7)
(30m+19)(30k+23)=30p+437=30(p+14)+17=(30a-11)(30b-7)
8)
(30m+19)(30k+29)=30p+551=30(p+18)+11=(30a-11)(30b-1)



1)
(30m+23)(30k+1)=30p+23=(30a-7)(30b-29)
2)
(30m+23)(30k+7)=30p+161=30(p+5)+11=(30a-7)(30b-23)
3)
(30m+23)(30k+11)=30p+253=30(p+8)+13=(30a-7)(30b-19)
4)
(30m+23)(30k+13)=30p+299=30(p+9)+29=(30a-7)(30b-17)
5)
(30m+23)(30k+17)=30p+391=30(p+13)+1=(30a-7)(30b-13)
6)
(30m+23)(30k+19)=30p+437=30(p+14)+17=(30a-7)(30b-11)
7)
(30m+23)(30k+23)=30p+529=30(p+17)+19=(30a-7)(30b-7)
8)
(30m+23)(30k+29)=30p+667=30(p+22)+7=(30a-7)(30b-1)



1)
(30m+29)(30k+1)=30p+29=(30a-1)(30b-29)
2)
(30m+29)(30k+7)=30p+203=30(p+6)+23=(30a-1)(30b-23)
3)
(30m+29)(30k+11)=30p+319=30(p+10)+19=(30a-1)(30b-19)
4)
(30m+29)(30k+13)=30p+377=30(p+12)+17=(30a-1)(30b-17)
5)
(30m+29)(30k+17)=30p+493=30(p+16)+13=(30a-1)(30b-13)
6)
(30m+29)(30k+19)=30p+551=30(p+18)+11=(30a-1)(30b-11)
7)
(30m+29)(30k+23)=30p+667=30(p+22)+7=(30a-1)(30b-7)
8)
(30m+29)(30k+29)=30p+841=30(p+28)+1=(30a-1)(30b-1)

これで
(30n+p)=(30m+q)(30k+r)
(30n+p)=(30m-q)(30k-r)

の証明終わり｡

1)
(30m+1)(30k-1)=30p-1=30(p-1)+29=(30a-29)(30b+29)
2)
(30m+1)(30k-7)=30p-7=30(p-1)+23=(30a-29)(30b+23)
3)
(30m+1)(30k-11)=30p-11=30(p-1)+19=(30a-29)(30b+19)
4)
(30m+1)(30k-13)=30p-13=30(p-1)+17=(30a-29)(30b+17)
5)
(30m+1)(30k-17)=30p-17=30(p-1)+13=(30a-29)(30b+13)
6)
(30m+1)(30k-19)=30p-19=30(p-1)+11=(30a-29)(30b+11)
7)
(30m+1)(30k-23)=30p-23=30(p-1)+7=(30a-29)(30b+7)　
8)
(30m+1)(30k-29)=30p-29=30(p-1)+1=(30a-29)(30b+1)　

以下において30p-c=30(p-1)+d(ただし、d=30-c)の変換は省略する｡

1)
(30m+7)(30k-1)=30p-7=(30a-13)(30b+29)
2)
(30m+7)(30k-7)=30p-49=30(p-1)-19=(30a-13)(30b+23)
3)
(30m+7)(30k-11)=30p-77=30(p-2)-17=(30a-13)(30b+19)
4)
(30m+7)(30k-13)=30p-91=30(p-3)-1=(30a-13)(30b+17)
5)
(30m+7)(30k-17)=30p-119=30(p-3)-29=(30a-13)(30b+13)
6)
(30m+7)(30k-19)=30p-133=30(p-4)-13=(30a-13)(30b+11)
7)
(30m+7)(30k-23)=30p-161=30(p-5)-11=(30a-13)(30b+7)
8)
(30m+7)(30k-29)=30p-203=30(p-6)-23=(30a-13)(30b+1)



1)
(30m+11)(30k-1)=30p-11=(30a-19)(30b29)
2)
(30m+11)(30k-7)=30p-77=30(p-2)-17=(30a-19)(30b+23)
3)
(30m+11)(30k-11)=30p-121=30(p-4)-1=(30a-19)(30b+19)
4)
(30m+11)(30k-13)=30p-143=30(p-4)-23=(30a-19)(30b+17)
5)
(30m+11)(30k-17)=30p-187=30(p-6)-7=(30a-19)(30b+13)
6)
(30m+11)(30k-19)=30p-209=30(p-6)-29=(30a-19)(30b+11)
7)
(30m+11)(30k-23)=30p-253=30(p-8)-11=(30a-19)(30b+7)
8)
(30m+11)(30k-29)=30p-319=30(p-10)-19=(30a-19)(30b+1)



1)
(30m+13)(30k-1)=30p-13=(30a-17)(30b+29)
2)
(30m+13)(30k-7)=30p-91=30(p-3)-1=(30a-17)(30b+23)
3)
(30m+13)(30k-11)=30p-143=30(p-4)-23=(30a-17)(30b+19)
4)
(30m+13)(30k-13)=30p-169=30(p-5)-19=(30a-17)(30b+17)
5)
(30m+13)(30k-17)=30p-221=30(p-7)-11=(30a-17)(30b+13)
6)
(30m+13)(30k-19)=30p-247=30(p-8)-7=(30a-17)(30b+11)
7)
(30m+13)(30k-23)=30p-299=30(p-9)-29=(30a-17)(30b+7)
8)
(30m+13)(30k-29)=30p-377=30(p-12)-17=(30a-17)(30b+1)



1)
(30m+17)(30k-1)=30p-17=(30a-13)(30b+29)
2)
(30m+17)(30k-7)=30p-119=30(p-6)-19=(30a-13)(30b+23)
3)
(30m+17)(30k-11)=30p-187=30(p-6)-7=(30a-13)(30b+19)
4)
(30m+17)(30k-13)=30p-221=30(p-7)-11=(30a-13)(30b+17)
5)
(30m+17)(30k-17)=30p-289=30(p-9)-19=(30a-13)(30b+13)
6)
(30m+17)(30k-19)=30p-323=30(p-10)-23=(30a-13)(30b+11)
7)
(30m+17)(30k-23)=30p-391=30(p-13)-1=(30a-13)(30b+7)
8)
(30m+17)(30k-29)=30p-493=30(p-16)-13=(30a-13)(30b+1)



1)
(30m+19)(30k-1)=30p-19=(30a-11)(30b+29)
2)
(30m+19)(30k-7)=30p-133=30(p-4)-11=(30a-11)(30b+23)
3)
(30m+19)(30k-11)=30p-209=30(p-6)-29=(30a-11)(30b+19)
4)
(30m+19)(30k-13)=30p-247=30(p-8)-7=(30a-11)(30b+17)
5)
(30m+19)(30k-17)=30p-323=30(p-10)-23=(30a-11)(30b+13)
6)
(30m+19)(30k-19)=30p-361=30(p-12)-1=(30a-11)(30b+11)
7)
(30m+19)(30k-23)=30p-437=30(p-14)-17=(30a-11)(30b+7)
8)
(30m+19)(30k-29)=30p-551=30(p-18)-11=(30a-11)(30b+1)



1)
(30m+23)(30k-1)=30p-23=(30a-7)(30b+29)
2)
(30m+23)(30k-7)=30p-161=30(p-5)-11=(30a-7)(30b+23)
3)
(30m+23)(30k-11)=30p-253=30(p-8)-13=(30a-7)(30b+19)
4)
(30m+23)(30k-13)=30p-299=30(p-9)-29=(30a-7)(30b+17)
5)
(30m+23)(30k-17)=30p-391=30(p-13)-1=(30a-7)(30b+13)
6)
(30m+23)(30k-19)=30p-437=30(p-14)-17=(30a-7)(30b+11)
7)
(30m+23)(30k-23)=30p-529=30(p-17)-19=(30a-7)(30b+7)
8)
(30m+23)(30k-29)=30p-667=30(p-22)-7=(30a-7)(30b+1)



1)
(30m+29)(30k-1)=30p-29=(30a-1)(30b+29)
2)
(30m+29)(30k-7)=30p-203=30(p-6)-23=(30a-1)(30b+23)
3)
(30m+29)(30k-11)=30p-319=30(p-10)-19=(30a-1)(30b+19)
4)
(30m+29)(30k-13)=30p-377=30(p-12)-17=(30a-1)(30b+17)
5)
(30m+29)(30k-17)=30p-493=30(p-16)-13=(30a-1)(30b+13)
6)
(30m+29)(30k-19)=30p-551=30(p-18)-11=(30a-1)(30b+11)
7)
(30m+29)(30k-23)=30p-667=30(p-22)-7=(30a-1)(30b+7)
8)
(30m+29)(30k-29)=30p-841=30(p-28)-1=(30a-1)(30b+1)

なお、30(p-w)-sは正の数であることに注意｡


これで
(30n-p)=(30m+q)(30k-r)
(30n-p)=(30m-q)(30k+r)

の証明終わり｡

もともと最初の表には30n±1、30n±7、30n±11、30n±13の数ですが素数でないものは、素数と素数の積ですから
素数でないものは、素数×（30n±1、30n±7、30n±11、30n±13）の数しかないことを証明しました｡

さて、エラトステネスの篩ですが


これは,7の倍数が黄色に塗ってあります｡縦に等間隔で並びます｡

これは１１の倍数の表です｡同じく縦に並びます｡

これは
＝＝＝＝＝掲示板より＝＝＝＝＝＝＝
30n+Qがなぜ縦に並ぶかの証明｡

素数30m+qの倍数は、縦に並ぶとき横は30ですから30*(30m+q)=30*30m+30qより縦に並びます｡
今,その間のj/kにあるとすると縦に並ぶとき横は30ですから
30*(30m+q)*j/k=30*(30m*j/k)+30*q*j/k
となります｡j/k<1なのでq*j/k<q
よって,30q*j/k<30qとなり,縦には並ばないことになります｡
すると,その間のj/kにあるとすることはできません｡
したがって,素数30m+qの倍数は30m+qごとに並びます｡

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
より、全ての素数の倍数に成り立ちます｡

したがって,

＝＝＝＝＝掲示板より＝＝＝＝＝＝＝
まず、30n+Qの表を作る｡
まず表の最初の数７を取り出し、7に30n+Qの表のはじめの数すなわち7をかける｡49を得る｡
(7x7)　mod　30=49　mod　30=19　より、49のあとは56個おきに表の全ての数を消す｡
次に表から11を得る｡
(7x11)　mod　30=77　mod　30=17より、77のあとは56個おきに表の全ての数を消す｡
次に表から13を得る｡
(7x13)　mod　30=91　mod　30=1より、91のあとは56個おきに表の全ての数を消す｡
このように8つの列を全て処理すれば,7の倍数は除かれる｡

次に,表から7の次の11を得る。
(11x11)　mod　30=121　mod　30=1　より、121のあとは88個おきに表の全ての数を消す｡
次に表から13を得る｡
(11x13)　mod　30=143　mod　30=23より、143のあとは88個おきに表の全ての数を消す｡
このように8つの列を全て処理すれば,11の倍数は除かれる｡

これを30n+Qの表の残っている数をはじめから全てやれば完了する｡
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

となります｡

32bitの符号付き整数で表わせる最大値に設定してあります。しらみつぶし法と一致することを確認しています。

Ubuntu20.04で

$ gcc -Wall -O2 -o sosuu-3.max sosuu-3.max.c
$ ./sosuu-3.max
篩=46337 経過時間= 1 分 8 秒
now saving  disk file!
素数個数=105080509


となりました。

この計算にメモリは、2.4GBytesくらい使います。

エラトステネス篩法によるsosuu-3.max.c のダウンロード

出力は、sosuuhyoというファイルです。約1.1GBytesです。

素数が1行8個並んだテキストファイルです。

つづく

メインページに戻る