|
|
エラトステネスのふるい(6n+k)
LET N=5
FOR I=1 TO 10
LET E=I*10^N
LET PE=PRIMECOUNT(E)
PRINT S+1;"～";E;":";PE-PS;PE
LET S=E
LET PS=PE
NEXT I
END
EXTERNAL FUNCTION PRIMECOUNT(N)
DIM A(2),P(N)
MAT READ A
! ２・３を特別扱い
DATA 1,5
FOR I=0 TO INT(SQR(N)/6) ! ループ SQR(N)*2/6=SQR(N)/3
FOR J=1 TO 2
IF I=0 AND J=1 THEN LET J=2
LET K=6*I+A(J)
IF N<K THEN EXIT FOR
IF P(K)=0 THEN
FOR L=K*K TO N STEP K*2
LET P(L)=1
NEXT L
END IF
NEXT J
NEXT I
LET COUNT=2 ! 2 3
FOR I=0 TO INT(N/6)
FOR J=1 TO 2
IF I=0 AND J=1 THEN LET J=2
LET K=6*I+A(J)
IF N<K THEN EXIT FOR
IF P(K)=0 THEN LET COUNT=COUNT+1
NEXT J
NEXT I
LET PRIMECOUNT=COUNT
END FUNCTION
https://en.wikipedia.org/wiki/Wheel_factorization
2n+k 1/2 ２を特別扱い
6n+k 2/6=1/3 ２,３を特別扱い
30n+k 8/30=1/3.75 ２,３,５を特別扱い
210n+k 48/210=1/4.375 ２,３,５,７を特別扱い
2310n+k 480/2310=1/4.8125 ２,３,５,７,１１を特別扱い
30030n+k 5760/30030=1/5.21354166666667 ２,３,５,７,１１,１３を特別扱い
510510n+k 92160/510510=1/5.53938802083333 ２,３,５,７,１１,１３,１７を特別扱い
9699690n+k 1658880/9699690=1/5.84713179976852 ２,３,５,７,１１,１３,１７,１９を特別扱い
223092870n+k 36495336/223092870=1/6.112914537901501 ２,３,５,７,１１,１３,１７,１９,２３を特別扱い
素数階乗(素数積)以外では
60n+k(1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59) の16個となり16/60=1/3.75
つまり30n+kと計算量は同じになります
10n+k(1,3,7,9) 4/10=1/2.5
100n+k(1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,51,53,57,59,61,63,67,69,71,73,77,79,81,83,87,89,91,93,97,99) の40個係数が必要で
40/100=1/2.5となり 6n+k(1,5) 2/6=1/3 6n+kよりも計算量が多くなります。
6n+k(1,5),6n+k(5,7),6n+k(-1,1),6n+k(-5,-1)でも計算可能です(nの範囲が異なります)
係数の求め方
30n+kでn=0,1,2,...とした時、30n+kが素数になるkを求めます。
30n+1 : 31,61,151...素数
30n+2 : 2で割れる
30n+3 : 3で割れる
30n+5 : 5で割れる
30n+7 : 7,37,67...素数
30n+9 : 3で割れる
30n+11: 11,41,71...素数
30n+13: 13,43,73...素数
30n+15: 15で割れる
30n+17: 17,47,107...素数
30n+19: 19,79,109...素数
30n+21: 3で割れる
30n+23: 23,53,73...素数
30n+25: 5で割れる
30n+27: 3で割れる
30n+29: 29,59,89...素数
よって
30n+k(1,7,11,13,17,19,23,29)となります
30n+k(7,11,13,17,19,23,29,31)でも計算できます
|
|