mod(6n+3,3)=0, 6n-1,6n+1以外から素数は出ません。

 投稿者：たろさ  投稿日：2021年 9月15日(水)18時53分24秒
  ! 6n±1篩　Ver.2
OPTION ARITHMETIC NATIVE       !2進モード
LET t0=TIME
LET k=1E8         !1E7   9999991 素数 (664579th)
LET k1=IP(k/6)    !1E8  99999989 素数 (5761455th)
LET k2=IP(SQR(k1))!5E8 499999993 素数 (26355867th)
DIM A5(k1),A7(k1)

MAT A5=ZER
MAT A7=ZER

LET P1=5
LET C1=1

DO
   FOR n=1 TO k1
      LET P6=P1*n+C1
      IF P6 > k1 THEN EXIT FOR
      LET A5(P6)=1
   NEXT n
   FOR n=1 TO k1
      LET P6=P1*n-C1
      IF P6 > k1 THEN EXIT FOR
      LET A7(P6)=1
   NEXT n

   LET P1=P1+6
   LET C1=C1+1
   IF P1 >k1 THEN EXIT DO
LOOP


LET P1=7
LET C1=1
DO
   FOR n=1 TO k1
      LET P6=P1*n+C1
      IF P6 > k1 THEN EXIT FOR
      LET A7(P6)=1
   NEXT n

   FOR n=1 TO k1
      LET P6=P1*n-C1
      IF P6 > k1 THEN EXIT FOR
      LET A5(P6)=1
   NEXT n

   LET P1=P1+6
   LET C1=C1+1
   IF P1 >k1 THEN EXIT DO
LOOP
PRINT "2"
PRINT "3"
LET c=2
FOR n=1 TO k1
   LET P5=6*n-1
   LET P7=6*n+1
   IF A5(n)=0 THEN
      LET c=c+1
      IF k-1000<P5 THEN PRINT P5
   END IF
   IF A7(n)=0 THEN
      LET c=c+1
      IF k-1000<P7 THEN PRINT P7
   END IF
NEXT n

PRINT c
LET TM=TIME-t0
PRINT TM;"秒"

END

計算結果

2
3
99999043
99999073
99999077
99999079
99999089
99999103
99999113
99999131
99999157
99999167
99999187
99999217
途中省略
99999931
99999941
99999959
99999971
99999989
5761455
4.438000000009 秒
BASIC Accelerator Ver. 1.2.0.5 (2020.03.31)

mod(6n+3,3)=0　は正しいと思うので
6n-1,6n+1　以外から素数は出ません。 		 

戻る