素数積篩 210n+k

 投稿者:たろさ  投稿日:2021年11月 7日(日)19時45分32秒
  !210n+k篩
OPTION ARITHMETIC NATIVE
LET t0=TIME

LET k=316241   !MAX 100,008,370,081
LET k2=27294
DIM P(k)
DIM A(k2) !素数
SUB prime(v)  !エラトステネスの奇数列篩
   LET k9=v
   LET h1=1
   LET A(h1)=2
   LET h1=2
   FOR n1=3 TO k9 STEP 2
      IF P(n1)=0 THEN
         LET A(h1)=n1
         LET h1=h1+1
         IF h1>k9+1 THEN GOTO 20
      END IF
      FOR k1=n1 TO k9 STEP 2
         LET m1=n1*k1
         IF m1>k9 THEN GOTO 10
         LET P(m1)=1
      NEXT k1
10    NEXT n1
20
   END SUB
   CALL prime(k)



   DIM B(48)
   DATA 1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109
   DATA 113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209

   MAT READ B

   LET Q=210         !1E8=5761455(0.28秒)
   LET k1=1E8        !1E9=50847534(3.96秒) 1E6=78498
   LET ka=IP(k1/Q )  !1E10=455052511(54.25秒)
   LET kb=k1         !1E11=4118054813(686.84秒)11分26秒84 (686.93秒)
   LET kc=IP(SQR(k1))      !1E+8=1229, 1E+7=447
   LET kd=IP(ka/11+11)
   DIM D(ka)


   LET k3=0
   FOR n=1 TO k2
      LET PP=A(n)
      IF PP > kc THEN EXIT FOR
      LET k3=k3+1
   NEXT n
   !PRINT "k3=";k3;kc

   LET cj =46

   FOR r=1 TO 48
      LET rr=B(r)
      MAT D = ZER

      FOR t=5 TO k3
         LET x=A(t)   !素数篩
         IF x^2 >  k1 THEN EXIT FOR


         IF MOD(x-rr,Q)=0 THEN
            LET y=(x-rr)/Q
            FOR f=1 TO kd
               LET ii=x*f+y
               IF ii>ka THEN EXIT FOR
               LET D(ii)=1
            NEXT f

         ELSE

            FOR i=1 TO 48
               LET rv=B(i)
               IF MOD(x*rv+rr,Q)=0 THEN
                  LET y=-(x*rv+rr)/Q
                  EXIT FOR
               END IF
            NEXT i

            FOR f=1 TO kd
               LET ii=x*f+y
               IF ii > ka THEN EXIT FOR
               IF ii <= 0 THEN GOTO 100
               LET D(ii)=1
100          NEXT f
          END IF
          !PRINT x;kd;f;ii;ka
       NEXT t

       FOR n=1 TO ka
          IF n*Q+rr>k1   THEN EXIT FOR
          IF D(n)=0 THEN LET cj=cj+1
       NEXT n
    NEXT r

    PRINT cj
    LET TM=TIME-t0
    PRINT USING"####." & REPEAT$("#",2):TM;
    PRINT "秒"
END

動作報告です。

Paract BASIC プログラム  210n+k篩  素数の個数を数えるプログラム

動作環境
Intel Core i7 -8565U    mouse m-Book MB-R500 ノート PC

Windows Version
Microsoft Windows 10 (10.0) Professional 64-bit

Paract BASIC Ver. 2.1.2.4 Rev.2   (2021.06.19)

Lazarus fpc-3.2.2-win64
lazarus-2.2.0RC1-fpc-3.2.2-win64.exe               2021-07-08 199.7 MB
lazarus-2.2.0RC1-fpc-3.2.2-cross-i386-win32-win64.exe 2021-07-08  55.1 MB
 

戻る