十進BASICプログラム 6n-1,6n+1 素数の個数を数える

6n-1,6n+1 素数の個数を数える

!6n+k
OPTION ARITHMETIC NATIVE

DECLARE EXTERNAL SUB prime
LET k=3E8
CALL prime(k)
END

EXTERNAL SUB prime(k)
OPTION ARITHMETIC NATIVE

!エラトステネスの篩
LET Fu=17783
LET Fm=2040
DIM P(Fu)
DIM A(Fm)
MAT P=ZER
MAT A=ZER
LET A(1)=2
LET H1=1
FOR I=3 TO SQR(Fu) STEP 2
   IF P(I)=0 THEN
      FOR J=I*I TO Fu STEP I
         LET P(J)=1
      NEXT J
   END IF
NEXT I
FOR I=3 TO Fu STEP 2
   IF P(I)=0 THEN
      LET H1=H1+1
      LET A(H1)=I
   END IF
NEXT I
 
LET Q=6
LET k5=IP(k/Q)
DIM Au(k5),Av(k5)
 
MAT Au = ZER     !(6*n-1)
MAT Av = ZER     !(6*n+1)
 
FOR P1=3 TO k/6
   LET P2=A(P1)
   LET P3=A(P1+1)
   IF P2^2>k THEN EXIT FOR
   LET m= (P2^2-1)/ 6
   DO 
      LET Av(m)=1        !(6*n+1)
      LET m=m+p2
      IF m>k5 THEN EXIT DO 
   LOOP 
   IF MOD(P2*P3+1,6)=0 THEN 
      LET w= (P2*P3+1)/ 6
   ELSE
      LET P3=A(P1)
      DO 
         LET P3=P3+1
         IF MOD(P2*P3+1,6)=0 THEN EXIT DO
      LOOP
      LET w= (P2*P3+1)/ 6
      ! PRINT   P2;P3;P2*P3+1
   END IF
   DO 
      LET Au(w)=1        !(6*n-1)
      LET w=w+p2
      IF w>k5 THEN EXIT DO 
   LOOP
NEXT p1
!PRINT 2
!PRINT 3
LET cc=2
FOR n=1 TO k5     
   IF Au(n)=0 THEN 
      LET cc=cc+1
      LET L= 6*n-1
      !PRINT L         !(6*n-1)
   END IF 
   IF Av(n)=0 THEN 
      LET cc=cc+1
      LET R= 6*n+1
      !PRINT R         !(6*n+1)
   END IF
NEXT n
print cc
END SUB                      

計算結果

 16252325 　3億までの素数の個数

数学的に

素数の  Pn^2  は　6*n-1　例:  5×5=25    4×6=24    24+1=25

素数積の　Pn×Pn+1  は　6*n+1　例:  5×7=35    6×6=36    36-1=35

無限ループ