四つ子素数生成プログラム

 投稿者：たろさ  投稿日：2017年 4月12日(水)18時46分37秒
  四つ子素数（よつごそすう、英: prime quadruplet）とは、
4個の素数の組で、(p, p + 2, p + 6, p + 8) のタイプ。四つ子素数Wikipediaより

31から10億間の四つ子素数は28388-2個
http://oeis.org/A050258/b050258.txt


下記のプログラムは、31から10億間の四つ子素数をカウント
101,以上の最初の数
リストを生成

BASIC Acc　Ver. 0.9.8.1　 Lazarus 1.6.4 (FPC 3.0.2)を使用しました。

!30n± k篩 prime quadruplet
OPTION ARITHMETIC NATIVE
LET t0=TIME
LET k6=31627
LET k2=3402
!エラトステネスの篩
LET Fu=k6
DIM P(Fu)
DIM A(k2) !素数
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

DIM B(4)
DATA 11,13,17,19
MAT READ B

LET Q=30
LET ka=IP(1E9/Q)+1
LET kb=1E9
LET kc=k2
LET kd=IP(kb/207)

DIM D(ka)
DIM E(ka)

LET cj=2     !(5, 7, 11, 13, 17),  (11, 13, 17, 19, 23),

FOR r=1 TO 4
   LET rr=B(r)
   MAT D = ZER
   FOR t=4 TO kc
      LET x=A(t)

      IF MOD(x+rr,Q)=0 THEN
         LET y=-(x+rr)/Q
         GOTO 80
      END IF

      IF MOD(x-rr,Q)=0 THEN
         LET y=(x-rr)/Q
         GOTO 80
      END IF

      FOR i=2 TO x !*.86
         IF MOD(Q*i-rr,x)=0 THEN
            LET y=-i
            EXIT FOR
         END IF
      NEXT i

80       FOR f=1 TO kd
            IF x*f+y>ka THEN EXIT FOR
            LET D(x*f+y)=1
         NEXT f
      NEXT t

      MAT E=D+E
   NEXT r
   OPEN #1:NAME "E:\prime_10_PQF.txt",RECTYPE INTERNAL
   ERASE #1

   WRITE #1: 5
   WRITE #1: 11
   FOR n=1 TO ka
      IF n*Q+rr>kb THEN EXIT FOR
      IF E(n)=0 THEN
         LET cj=cj+1
         WRITE #1: 30*n+11
      END IF
   NEXT n
   CLOSE #1
   PRINT cj
   LET TM=TIME-t0
   PRINT USING"####." & REPEAT$("#",2):TM;
   PRINT "秒"
END


100億以上でも高速に計算できるプログラムを模索しています。

Re: 30n± k篩　#4283

http://blogs.yahoo.co.jp/donald_stinger

  

Re: 四つ子素数生成プログラム

 投稿者：しばっち  投稿日：2017年 4月13日(木)19時31分24秒
  > No.4298[元記事へ]

たろささんへのお返事です。

これはエラトステネスの篩ですが、HDDより素数リストを読み込みながら
処理しています。予め素数リストをご用意ください。
有理数モードを使用して、2を除外しメモリーを半分にしています。

下記よりdllファイルをダウンロードしてください

四つ子素数の条件、最小のもの以外は30n + 11, 30n + 13, 30n + 17, 30n + 19より
11引いて30で割り切れる開始値以上の最小値から30ステップずつ探索しています。

OPTION ARITHMETIC RATIONAL
LET S=1000000000000001 !'開始値(奇数)
LET E=S+100000000      !'終了値
LET P=GetArray((E-S)/2)
IF P<>0 THEN
   LET T=TIME
   OPEN #1:NAME "prime_list.txt"
   LET K=INTSQR(E)+1
   DO
      INPUT #1,IF MISSING THEN EXIT DO:A
      IF A>2 THEN
         IF A>K THEN EXIT DO
         IF MOD(S,A)>0 THEN LET S1=INT(S/A+1)*A ELSE LET S1=S
         IF S<=A THEN
            IF Test(p,(S1-S)/2)=0 THEN LET S1=S1+A
         END IF
         FOR I=S1 TO E STEP A
            IF MOD(I,2)=1 THEN CALL SetBit(P,(I-S)/2) !'奇数のみセット
         NEXT I
      END IF
   LOOP
   CLOSE #1
   PRINT USING "####.##秒":MOD(TIME-T+86400,86400)
   LET T=TIME
   OPEN #1:NAME "out.txt"
   ERASE #1
   LET S1=INT((S-11)/30+1)*30+11
   FOR I=S1 TO E-8 STEP 30
      IF Test(p,(I-S)/2)=0 AND Test(p,(I-S+2)/2)=0 AND Test(p,(I-S+6)/2)=0 AND Test(p,(I-S+8)/2)=0 THEN
         LET COUNT=COUNT+1
         PRINT #1:I;I+2;I+6;I+8
      END IF
   NEXT I
   PRINT #1:"COUNT=";COUNT
   CLOSE #1
   CALL FreeArray(p)
   PRINT USING "####.##秒":TIME-T
END IF
END

EXTERNAL FUNCTION GetArray(s)
OPTION ARITHMETIC RATIONAL
! (s+1)ビットのメモリを確保し，ゼロで埋める。
! 結果は，メモリのアドレス。0のときは失敗。
FUNCTION GetArray_sub(s)
   ASSIGN "BitArray.DLL","GetArray"
END FUNCTION
IF 0<=s AND s<2^32 THEN
   LET GetArray=getArray_sub(s)
ELSE
   LET GetArray=0
END IF
END FUNCTION

EXTERNAL SUB FreeArray(p)
OPTION ARITHMETIC RATIONAL
! メモリを返却する。pはGetArrayで得た値
ASSIGN "BitArray.DLL","FreeArray"
END SUB

EXTERNAL FUNCTION Test(p,i)
OPTION ARITHMETIC RATIONAL
! i番目のビットを取得する。pはGetArrayで得た値
ASSIGN "BitArray.DLL", "Test"
END FUNCTION

EXTERNAL SUB SetBit(p,i)
OPTION ARITHMETIC RATIONAL
! i番目のビットを1にする。pはGetArrayで得た値
ASSIGN "BitArray.DLL", "SetBit"
END SUB

EXTERNAL SUB ResetBit(p,i)
OPTION ARITHMETIC RATIONAL
! i番目のビットを0にする。pはGetArrayで得た値
ASSIGN "BitArray.DLL", "ResetBit"
END SUB

実行結果

1000000000067441  1000000000067443  1000000000067447  1000000000067449
1000000001137931  1000000001137933  1000000001137937  1000000001137939
1000000001519411  1000000001519413  1000000001519417  1000000001519419
1000000001794691  1000000001794693  1000000001794697  1000000001794699
1000000001800691  1000000001800693  1000000001800697  1000000001800699
1000000002108461  1000000002108463  1000000002108467  1000000002108469
1000000002504311  1000000002504313  1000000002504317  1000000002504319
1000000002620231  1000000002620233  1000000002620237  1000000002620239
1000000002905081  1000000002905083  1000000002905087  1000000002905089
1000000003185641  1000000003185643  1000000003185647  1000000003185649
1000000004045171  1000000004045173  1000000004045177  1000000004045179
1000000005134021  1000000005134023  1000000005134027  1000000005134029
1000000005257171  1000000005257173  1000000005257177  1000000005257179
1000000005356081  1000000005356083  1000000005356087  1000000005356089
1000000005641471  1000000005641473  1000000005641477  1000000005641479
1000000005747101  1000000005747103  1000000005747107  1000000005747109
1000000006151051  1000000006151053  1000000006151057  1000000006151059
1000000006915991  1000000006915993  1000000006915997  1000000006915999
1000000007149601  1000000007149603  1000000007149607  1000000007149609
1000000008859121  1000000008859123  1000000008859127  1000000008859129
1000000009052501  1000000009052503  1000000009052507  1000000009052509
1000000009108181  1000000009108183  1000000009108187  1000000009108189
1000000009898171  1000000009898173  1000000009898177  1000000009898179
1000000009903331  1000000009903333  1000000009903337  1000000009903339
1000000010588561  1000000010588563  1000000010588567  1000000010588569
1000000010792171  1000000010792173  1000000010792177  1000000010792179
1000000011636881  1000000011636883  1000000011636887  1000000011636889
1000000012201031  1000000012201033  1000000012201037  1000000012201039
1000000012324301  1000000012324303  1000000012324307  1000000012324309
1000000012594901  1000000012594903  1000000012594907  1000000012594909
1000000012673111  1000000012673113  1000000012673117  1000000012673119
1000000012802381  1000000012802383  1000000012802387  1000000012802389
1000000013026121  1000000013026123  1000000013026127  1000000013026129
1000000013139551  1000000013139553  1000000013139557  1000000013139559
1000000013372201  1000000013372203  1000000013372207  1000000013372209
1000000013439521  1000000013439523  1000000013439527  1000000013439529
1000000013456021  1000000013456023  1000000013456027  1000000013456029
1000000014204461  1000000014204463  1000000014204467  1000000014204469
1000000014272291  1000000014272293  1000000014272297  1000000014272299
1000000014669581  1000000014669583  1000000014669587  1000000014669589
1000000015499201  1000000015499203  1000000015499207  1000000015499209
1000000015513781  1000000015513783  1000000015513787  1000000015513789
1000000015548761  1000000015548763  1000000015548767  1000000015548769
1000000015885691  1000000015885693  1000000015885697  1000000015885699
1000000016331221  1000000016331223  1000000016331227  1000000016331229
1000000016641601  1000000016641603  1000000016641607  1000000016641609
1000000016859791  1000000016859793  1000000016859797  1000000016859799
1000000017356141  1000000017356143  1000000017356147  1000000017356149
1000000017425831  1000000017425833  1000000017425837  1000000017425839
1000000017593651  1000000017593653  1000000017593657  1000000017593659
1000000017617891  1000000017617893  1000000017617897  1000000017617899
1000000018015631  1000000018015633  1000000018015637  1000000018015639
1000000018740971  1000000018740973  1000000018740977  1000000018740979
1000000018985111  1000000018985113  1000000018985117  1000000018985119
1000000019722001  1000000019722003  1000000019722007  1000000019722009
1000000020483041  1000000020483043  1000000020483047  1000000020483049
1000000021712381  1000000021712383  1000000021712387  1000000021712389
1000000022027261  1000000022027263  1000000022027267  1000000022027269
1000000022196311  1000000022196313  1000000022196317  1000000022196319
1000000022627321  1000000022627323  1000000022627327  1000000022627329
1000000022875541  1000000022875543  1000000022875547  1000000022875549
1000000023170171  1000000023170173  1000000023170177  1000000023170179
1000000023454301  1000000023454303  1000000023454307  1000000023454309
1000000023553121  1000000023553123  1000000023553127  1000000023553129
1000000023650651  1000000023650653  1000000023650657  1000000023650659
1000000024598711  1000000024598713  1000000024598717  1000000024598719
1000000025580371  1000000025580373  1000000025580377  1000000025580379
1000000026117971  1000000026117973  1000000026117977  1000000026117979
1000000026296561  1000000026296563  1000000026296567  1000000026296569
1000000026442421  1000000026442423  1000000026442427  1000000026442429
1000000026594551  1000000026594553  1000000026594557  1000000026594559
1000000027051931  1000000027051933  1000000027051937  1000000027051939
1000000027066121  1000000027066123  1000000027066127  1000000027066129
1000000027665251  1000000027665253  1000000027665257  1000000027665259
1000000027829261  1000000027829263  1000000027829267  1000000027829269
1000000027955561  1000000027955563  1000000027955567  1000000027955569
1000000028435201  1000000028435203  1000000028435207  1000000028435209
1000000029840521  1000000029840523  1000000029840527  1000000029840529
1000000030219241  1000000030219243  1000000030219247  1000000030219249
1000000030225451  1000000030225453  1000000030225457  1000000030225459
1000000030292771  1000000030292773  1000000030292777  1000000030292779
1000000030533521  1000000030533523  1000000030533527  1000000030533529
1000000030624871  1000000030624873  1000000030624877  1000000030624879
1000000030954151  1000000030954153  1000000030954157  1000000030954159
1000000031028071  1000000031028073  1000000031028077  1000000031028079
1000000031319251  1000000031319253  1000000031319257  1000000031319259
1000000031413631  1000000031413633  1000000031413637  1000000031413639
1000000031541521  1000000031541523  1000000031541527  1000000031541529
1000000031750171  1000000031750173  1000000031750177  1000000031750179
1000000031848661  1000000031848663  1000000031848667  1000000031848669
1000000032202511  1000000032202513  1000000032202517  1000000032202519
1000000032320951  1000000032320953  1000000032320957  1000000032320959
1000000032457841  1000000032457843  1000000032457847  1000000032457849
1000000032535781  1000000032535783  1000000032535787  1000000032535789
1000000032700391  1000000032700393  1000000032700397  1000000032700399
1000000032770741  1000000032770743  1000000032770747  1000000032770749
1000000033282301  1000000033282303  1000000033282307  1000000033282309
1000000033635851  1000000033635853  1000000033635857  1000000033635859
1000000034537921  1000000034537923  1000000034537927  1000000034537929
1000000034682371  1000000034682373  1000000034682377  1000000034682379
1000000035014171  1000000035014173  1000000035014177  1000000035014179
1000000035363611  1000000035363613  1000000035363617  1000000035363619
1000000035955181  1000000035955183  1000000035955187  1000000035955189
1000000036897151  1000000036897153  1000000036897157  1000000036897159
1000000037446301  1000000037446303  1000000037446307  1000000037446309
1000000038261311  1000000038261313  1000000038261317  1000000038261319
1000000038392681  1000000038392683  1000000038392687  1000000038392689
1000000038611921  1000000038611923  1000000038611927  1000000038611929
1000000039029911  1000000039029913  1000000039029917  1000000039029919
1000000039145951  1000000039145953  1000000039145957  1000000039145959
1000000039436681  1000000039436683  1000000039436687  1000000039436689
1000000039502201  1000000039502203  1000000039502207  1000000039502209
1000000039710431  1000000039710433  1000000039710437  1000000039710439
1000000039951811  1000000039951813  1000000039951817  1000000039951819
1000000040547881  1000000040547883  1000000040547887  1000000040547889
1000000040644601  1000000040644603  1000000040644607  1000000040644609
1000000040679971  1000000040679973  1000000040679977  1000000040679979
1000000041012521  1000000041012523  1000000041012527  1000000041012529
1000000041774491  1000000041774493  1000000041774497  1000000041774499
1000000041854831  1000000041854833  1000000041854837  1000000041854839
1000000041946811  1000000041946813  1000000041946817  1000000041946819
1000000042156721  1000000042156723  1000000042156727  1000000042156729
1000000042276091  1000000042276093  1000000042276097  1000000042276099
1000000042321991  1000000042321993  1000000042321997  1000000042321999
1000000042763921  1000000042763923  1000000042763927  1000000042763929
1000000042894661  1000000042894663  1000000042894667  1000000042894669
1000000043014361  1000000043014363  1000000043014367  1000000043014369
1000000043069141  1000000043069143  1000000043069147  1000000043069149
1000000044249251  1000000044249253  1000000044249257  1000000044249259
1000000044407051  1000000044407053  1000000044407057  1000000044407059
1000000044473321  1000000044473323  1000000044473327  1000000044473329
1000000044647831  1000000044647833  1000000044647837  1000000044647839
1000000044742661  1000000044742663  1000000044742667  1000000044742669
1000000044901931  1000000044901933  1000000044901937  1000000044901939
1000000045364891  1000000045364893  1000000045364897  1000000045364899
1000000045415801  1000000045415803  1000000045415807  1000000045415809
1000000045745801  1000000045745803  1000000045745807  1000000045745809
1000000046053361  1000000046053363  1000000046053367  1000000046053369
1000000046877521  1000000046877523  1000000046877527  1000000046877529
1000000047206051  1000000047206053  1000000047206057  1000000047206059
1000000047552041  1000000047552043  1000000047552047  1000000047552049
1000000047594011  1000000047594013  1000000047594017  1000000047594019
1000000047754241  1000000047754243  1000000047754247  1000000047754249
1000000048400201  1000000048400203  1000000048400207  1000000048400209
1000000048618391  1000000048618393  1000000048618397  1000000048618399
1000000048974461  1000000048974463  1000000048974467  1000000048974469
1000000049202851  1000000049202853  1000000049202857  1000000049202859
1000000049233811  1000000049233813  1000000049233817  1000000049233819
1000000049288501  1000000049288503  1000000049288507  1000000049288509
1000000049457371  1000000049457373  1000000049457377  1000000049457379
1000000049542601  1000000049542603  1000000049542607  1000000049542609
1000000049758271  1000000049758273  1000000049758277  1000000049758279
1000000050106901  1000000050106903  1000000050106907  1000000050106909
1000000050289181  1000000050289183  1000000050289187  1000000050289189
1000000050686801  1000000050686803  1000000050686807  1000000050686809
1000000050774911  1000000050774913  1000000050774917  1000000050774919
1000000051257041  1000000051257043  1000000051257047  1000000051257049
1000000051427051  1000000051427053  1000000051427057  1000000051427059
1000000052349161  1000000052349163  1000000052349167  1000000052349169
1000000052670341  1000000052670343  1000000052670347  1000000052670349
1000000052794271  1000000052794273  1000000052794277  1000000052794279
1000000053179291  1000000053179293  1000000053179297  1000000053179299
1000000053330821  1000000053330823  1000000053330827  1000000053330829
1000000053377441  1000000053377443  1000000053377447  1000000053377449
1000000053428261  1000000053428263  1000000053428267  1000000053428269
1000000053604751  1000000053604753  1000000053604757  1000000053604759
1000000053683201  1000000053683203  1000000053683207  1000000053683209
1000000053895691  1000000053895693  1000000053895697  1000000053895699
1000000053900431  1000000053900433  1000000053900437  1000000053900439
1000000053913571  1000000053913573  1000000053913577  1000000053913579
1000000054622531  1000000054622533  1000000054622537  1000000054622539
1000000054869461  1000000054869463  1000000054869467  1000000054869469
1000000054939931  1000000054939933  1000000054939937  1000000054939939
1000000055188991  1000000055188993  1000000055188997  1000000055188999
1000000055459591  1000000055459593  1000000055459597  1000000055459599
1000000056132521  1000000056132523  1000000056132527  1000000056132529
1000000056747401  1000000056747403  1000000056747407  1000000056747409
1000000056899021  1000000056899023  1000000056899027  1000000056899029
1000000057001501  1000000057001503  1000000057001507  1000000057001509
1000000057349591  1000000057349593  1000000057349597  1000000057349599
1000000057388861  1000000057388863  1000000057388867  1000000057388869
1000000057409621  1000000057409623  1000000057409627  1000000057409629
1000000057922861  1000000057922863  1000000057922867  1000000057922869
1000000058691911  1000000058691913  1000000058691917  1000000058691919
1000000058827331  1000000058827333  1000000058827337  1000000058827339
1000000059144011  1000000059144013  1000000059144017  1000000059144019
1000000059276131  1000000059276133  1000000059276137  1000000059276139
1000000059304991  1000000059304993  1000000059304997  1000000059304999
1000000061261561  1000000061261563  1000000061261567  1000000061261569
1000000061283491  1000000061283493  1000000061283497  1000000061283499
1000000061316491  1000000061316493  1000000061316497  1000000061316499
1000000061665061  1000000061665063  1000000061665067  1000000061665069
1000000061943521  1000000061943523  1000000061943527  1000000061943529
1000000062897371  1000000062897373  1000000062897377  1000000062897379
1000000062934721  1000000062934723  1000000062934727  1000000062934729
1000000063521881  1000000063521883  1000000063521887  1000000063521889
1000000063576601  1000000063576603  1000000063576607  1000000063576609
1000000063916591  1000000063916593  1000000063916597  1000000063916599
1000000064304671  1000000064304673  1000000064304677  1000000064304679
1000000065817931  1000000065817933  1000000065817937  1000000065817939
1000000066569851  1000000066569853  1000000066569857  1000000066569859
1000000066771421  1000000066771423  1000000066771427  1000000066771429
1000000067818721  1000000067818723  1000000067818727  1000000067818729
1000000068130571  1000000068130573  1000000068130577  1000000068130579
1000000068193541  1000000068193543  1000000068193547  1000000068193549
1000000068540281  1000000068540283  1000000068540287  1000000068540289
1000000068714791  1000000068714793  1000000068714797  1000000068714799
1000000069184111  1000000069184113  1000000069184117  1000000069184119
1000000069236191  1000000069236193  1000000069236197  1000000069236199
1000000069328171  1000000069328173  1000000069328177  1000000069328179
1000000070734781  1000000070734783  1000000070734787  1000000070734789
1000000070981201  1000000070981203  1000000070981207  1000000070981209
1000000071057131  1000000071057133  1000000071057137  1000000071057139
1000000071403511  1000000071403513  1000000071403517  1000000071403519
1000000072072031  1000000072072033  1000000072072037  1000000072072039
1000000072311431  1000000072311433  1000000072311437  1000000072311439
1000000072331081  1000000072331083  1000000072331087  1000000072331089
1000000072351541  1000000072351543  1000000072351547  1000000072351549
1000000072426931  1000000072426933  1000000072426937  1000000072426939
1000000072909001  1000000072909003  1000000072909007  1000000072909009
1000000072913291  1000000072913293  1000000072913297  1000000072913299
1000000073341931  1000000073341933  1000000073341937  1000000073341939
1000000074077441  1000000074077443  1000000074077447  1000000074077449
1000000074078821  1000000074078823  1000000074078827  1000000074078829
1000000074789341  1000000074789343  1000000074789347  1000000074789349
1000000074919121  1000000074919123  1000000074919127  1000000074919129
1000000075007231  1000000075007233  1000000075007237  1000000075007239
1000000075186571  1000000075186573  1000000075186577  1000000075186579
1000000075453781  1000000075453783  1000000075453787  1000000075453789
1000000075630091  1000000075630093  1000000075630097  1000000075630099
1000000075643201  1000000075643203  1000000075643207  1000000075643209
1000000076117171  1000000076117173  1000000076117177  1000000076117179
1000000076771951  1000000076771953  1000000076771957  1000000076771959
1000000077032261  1000000077032263  1000000077032267  1000000077032269
1000000077048821  1000000077048823  1000000077048827  1000000077048829
1000000077872351  1000000077872353  1000000077872357  1000000077872359
1000000077899231  1000000077899233  1000000077899237  1000000077899239
1000000078278581  1000000078278583  1000000078278587  1000000078278589
1000000078647461  1000000078647463  1000000078647467  1000000078647469
1000000078669721  1000000078669723  1000000078669727  1000000078669729
1000000078731761  1000000078731763  1000000078731767  1000000078731769
1000000079366591  1000000079366593  1000000079366597  1000000079366599
1000000079916281  1000000079916283  1000000079916287  1000000079916289
1000000080166511  1000000080166513  1000000080166517  1000000080166519
1000000080623231  1000000080623233  1000000080623237  1000000080623239
1000000081276451  1000000081276453  1000000081276457  1000000081276459
1000000081611821  1000000081611823  1000000081611827  1000000081611829
1000000082063231  1000000082063233  1000000082063237  1000000082063239
1000000082134631  1000000082134633  1000000082134637  1000000082134639
1000000082456981  1000000082456983  1000000082456987  1000000082456989
1000000082478581  1000000082478583  1000000082478587  1000000082478589
1000000082650601  1000000082650603  1000000082650607  1000000082650609
1000000082750561  1000000082750563  1000000082750567  1000000082750569
1000000082839391  1000000082839393  1000000082839397  1000000082839399
1000000082850071  1000000082850073  1000000082850077  1000000082850079
1000000083483251  1000000083483253  1000000083483257  1000000083483259
1000000083933701  1000000083933703  1000000083933707  1000000083933709
1000000083939581  1000000083939583  1000000083939587  1000000083939589
1000000084849091  1000000084849093  1000000084849097  1000000084849099
1000000085416721  1000000085416723  1000000085416727  1000000085416729
1000000085534711  1000000085534713  1000000085534717  1000000085534719
1000000085563511  1000000085563513  1000000085563517  1000000085563519
1000000086299441  1000000086299443  1000000086299447  1000000086299449
1000000086553841  1000000086553843  1000000086553847  1000000086553849
1000000086784241  1000000086784243  1000000086784247  1000000086784249
1000000087489301  1000000087489303  1000000087489307  1000000087489309
1000000087521971  1000000087521973  1000000087521977  1000000087521979
1000000088660561  1000000088660563  1000000088660567  1000000088660569
1000000089017351  1000000089017353  1000000089017357  1000000089017359
1000000089232091  1000000089232093  1000000089232097  1000000089232099
1000000089545921  1000000089545923  1000000089545927  1000000089545929
1000000090552031  1000000090552033  1000000090552037  1000000090552039
1000000090836821  1000000090836823  1000000090836827  1000000090836829
1000000091432801  1000000091432803  1000000091432807  1000000091432809
1000000091478251  1000000091478253  1000000091478257  1000000091478259
1000000091637641  1000000091637643  1000000091637647  1000000091637649
1000000091933741  1000000091933743  1000000091933747  1000000091933749
1000000092479231  1000000092479233  1000000092479237  1000000092479239
1000000092559001  1000000092559003  1000000092559007  1000000092559009
1000000092948671  1000000092948673  1000000092948677  1000000092948679
1000000093206461  1000000093206463  1000000093206467  1000000093206469
1000000093237331  1000000093237333  1000000093237337  1000000093237339
1000000093263551  1000000093263553  1000000093263557  1000000093263559
1000000093458851  1000000093458853  1000000093458857  1000000093458859
1000000093760531  1000000093760533  1000000093760537  1000000093760539
1000000094185661  1000000094185663  1000000094185667  1000000094185669
1000000094445041  1000000094445043  1000000094445047  1000000094445049
1000000094485541  1000000094485543  1000000094485547  1000000094485549
1000000095204821  1000000095204823  1000000095204827  1000000095204829
1000000096142141  1000000096142143  1000000096142147  1000000096142149
1000000096415861  1000000096415863  1000000096415867  1000000096415869
1000000097126081  1000000097126083  1000000097126087  1000000097126089
1000000097168951  1000000097168953  1000000097168957  1000000097168959
1000000097326031  1000000097326033  1000000097326037  1000000097326039
1000000097416511  1000000097416513  1000000097416517  1000000097416519
1000000097555861  1000000097555863  1000000097555867  1000000097555869
1000000097963681  1000000097963683  1000000097963687  1000000097963689
1000000098596921  1000000098596923  1000000098596927  1000000098596929
1000000099262441  1000000099262443  1000000099262447  1000000099262449
COUNT= 299
 		 

Re: 四つ子素数生成プログラム

 投稿者：たろさ  投稿日：2017年 4月14日(金)05時14分49秒
  > No.4301[元記事へ]

しばっちさんへのお返事です。

素晴らしいプログラムをありがとうございました。

動作報告
prime quadruples (30n+11, 30n+13, 30n+17, 30n+19).
30n+11=1000000000067441 TO 1000000099262441
299 個

1000兆までは、まだ遠いです。下記のプログラムを頼りにしています。
エラトステネスの篩            #4264
素数判定　Miller-Rabin法      #3894
エラトステネスの篩 eratos_dll #3985

Re: エラトステネスの篩　#4101
460000000000000 : 14054559347931 : 0
470000000000000 : 14350653588527 : 2958176
計算時間：6日と4時間33分46秒

-----------------------------------------------

下記は数値実験用プログラムです。


A014561 Numbers n giving rise to prime quadruples (30n+11, 30n+13, 30n+17, 30n+19).

上記の数列を生成するプログラム
prime quadruples　BASIC Acc program
-------------------------------
!30n± k篩
OPTION ARITHMETIC NATIVE
LET t0=TIME
LET k6=31627
LET k2=3402
!エラトステネスの篩 !#4264
LET Fu=k6
DIM P(Fu)
DIM A(k2) !素数
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

DIM B(4)
DATA 11,13,17,19
MAT READ B

LET Q=30
LET ka=INT(1E9/Q)+1
LET kb=1E9
LET kc=k2
LET kd=INT(kb/207)

DIM D(ka)
MAT D = ZER

LET cj=2     !(5, 7, 11, 13, 17),  (11, 13, 17, 19, 23),

FOR r=1 TO 4
   LET rr=B(r)
   FOR t=4 TO kc
      LET x=A(t)

      IF MOD(x+rr,Q)=0 THEN
         LET y=-(x+rr)/Q
         GOTO 80
      END IF

      IF MOD(x-rr,Q)=0 THEN
         LET y=(x-rr)/Q
         GOTO 80
      END IF

      FOR i=2 TO x !*.86
         IF MOD(Q*i-rr,x)=0 THEN
            LET y=-i
            EXIT FOR
         END IF
      NEXT i

80       FOR f=1 TO kd
            IF x*f+y>ka THEN EXIT FOR
            LET D(x*f+y)=1
         NEXT f
      NEXT t

   NEXT r
   OPEN #1:NAME "E:\pi4_1E_9.txt",RECTYPE INTERNAL
   ERASE #1
   WRITE #1:0
   FOR n=1 TO ka
      !IF n*Q+rr>kb THEN EXIT FOR
      IF D(n)=0 THEN
         LET cj=cj+1
         WRITE #1:n
      END IF
   NEXT n
   CLOSE #1
   PRINT cj
   LET TM=TIME-t0
   PRINT USING"####." & REPEAT$("#",2):TM;
   PRINT "秒"
END

-----------------------
計算結果

28388　  37.07秒

30n+k 篩　の探究の結果　このアルゴリズムにたどり着きました。

精度確認中です。

FOR i=2 TO x !*.86
         IF MOD(Q*i-rr,x)=0 THEN
            LET y=-i
            EXIT FOR
         END IF
      NEXT i

素数の係数を求めるループがネックで1000億位が限度です。

それで

6n±1 篩

十進BASIC 1000桁モードで 16桁も行ってみた。

!6n±1篩　Ver.1
!四つ子素数計数関数（π4(x) Prime Quadruplet-counting function）
DECLARE EXTERNAL FUNCTION cprime
DECLARE EXTERNAL SUB sqprime
OPTION ARITHMETIC DECIMAL_HIGH
PRINT DATE$;"/"; TIME$
LET t0=TIME

LET k=31716427
LET k2=1957369
DIM GT(k2)
OPEN #3:NAME "E:\prime_1E8xv.txt",ACCESS INPUT
FOR i=1 TO k2
   INPUT #3: GT(i)
NEXT i
CLOSE #3
! MAX  1005931741646329=31716427^2
LET SA=100000001 !MIN 2 (1E+7 to)
LET SB=100001000 !MAX  1E15-1
CALL sqprime(SA,SB,k2,GT)

DIM Bb(SA TO SB)
OPEN #2:NAME "prime_pi1.txt",ACCESS INPUT
FOR i=SA TO SB
   INPUT #2: BB(i)
NEXT i
CLOSE #2
!                      !SA=数値入力+1 (1E7)
LET c1=0               !1E7  (1E7)  to 2E7
PRINT SA-1;":";c2;":";c1;":";c
LET k6=SA*1E7-1E7
FOR n=SA TO SB
   LET t1=TIME
   LET k2=Bb(n) !π(x)
   LET k6=k6+1E7
   LET C=cprime(k2,k6,GT)
   LET c1=c1+c
   PRINT n*1E7;":";c2+c1;":";c1;":";c;
   LET TM=TIME-t1
   PRINT USING"######." & REPEAT$("#",2):TM;
   PRINT "秒"
NEXT n

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

EXTERNAL FUNCTION cprime (k2,k6,GT())
OPTION ARITHMETIC DECIMAL_HIGH
LET k4=k6-1E7
LET B6=INT(k6/30)
LET U=INT(k6/6)
LET W=INT(k4/6)
LET M7=W

DIM x(W-M7 TO U-M7)
MAT x = ZER !(6*n-1)

FOR n=3 TO k2
   LET P6=GT(n)
   LET G1=INT(W/P6)!-2
   IF MOD(P6+1,6)=0 THEN !(6*n-1)
      LET r6=(P6+1)/6
      FOR i=G1 TO B6
         IF P6*i+r6<W THEN GOTO 140
         IF P6*i+r6>U THEN EXIT FOR
         LET x(P6*i+r6-M7)=1
140       NEXT i
       END IF

       IF MOD(P6-1,6)=0 THEN
          LET r6=(P6-1)/6
          FOR i=G1 TO B6
             IF P6*i-r6<W THEN GOTO 150
             IF P6*i-r6>U THEN EXIT FOR
             LET x(P6*i-r6-M7)=1
150       NEXT i
       END IF

       IF MOD(P6+1,6)=0 THEN !(6*n+1)
          LET r6=(P6+1)/6
          FOR i=G1 TO B6
             IF P6*i-r6<W THEN GOTO 160
             IF P6*i-r6>U THEN EXIT FOR
             LET x(P6*i-r6-M7)=1
160       NEXT i
       END IF

       IF MOD(P6-1,6)=0 THEN
          LET r6=(P6-1)/6
          FOR i=G1 TO B6
             IF P6*i+r6<W THEN GOTO 170
             IF P6*i+r6>U THEN EXIT FOR
             LET x(P6*i+r6-M7)=1
170       NEXT i
       END IF
    NEXT n

    LET Cc=0
    FOR n=W-M7 TO U-M7-1
       LET ST=n+M7
       IF x(n)=0 AND x(n+1)=0 AND 6*ST-1>k4 AND 6*ST-1<k6 THEN
          LET cc=cc+1
       END IF
    NEXT n
    LET cprime=cc

END FUNCTION

EXTERNAL  SUB sqprime(SA,SB,k2,GT())
    OPTION ARITHMETIC DECIMAL_HIGH
    OPEN #2:NAME "prime_pi1.txt",RECTYPE INTERNAL
    ERASE #2
    LET x=1E7
    FOR i=1 TO k2-1
       LET v=GT(i)^2
       LET vi=GT(i+1)^2
       LET vv=vi-v
       IF x =< v THEN
          CALL sqrp(1)
          IF vv>=1E7 THEN
             LET vt=INT(vv/1E7)
             CALL sqrp(vt)
          END IF
       END IF
    NEXT i

    SUB sqrp(vo)
       FOR ns=1 TO vo
          LET C=C+1
          LET X=X+1E7
          IF C>=SA AND SB>=C THEN
             WRITE #2:i
          END IF
       NEXT ns
    END SUB
    CLOSE #2
END SUB

----------------------------------------------
双子素数-双子素数=6  配列にするとこのような状況

管理用メモリー限界のため一千万ループこれがネックです。

計算結果

100000000 : 3314576487 : 0 : 0
1000000010000000 : 3314576511 : 24 : 24
1000000020000000 : 3314576542 : 55 : 31
1000000030000000 : 3314576565 : 78 : 23
1000000040000000 : 3314576601 : 114 : 36
1000000050000000 : 3314576639 : 152 : 38
1000000060000000 : 3314576675 : 188 : 36
1000000070000000 : 3314576697 : 210 : 22
1000000080000000 : 3314576730 : 243 : 33
1000000090000000 : 3314576758 : 271 : 28
1000000100000000 : 3314576786 : 299 : 28

素数リストを読み込むので、遅いです。

計算時間　1千万あたり30秒*10　約300秒

Re: エラトステネスの篩　#4101

これでは、比較にならないです。

C++　のマルチプラットフォームも出来たらいいな～。

http://blogs.yahoo.co.jp/donald_stinger

  

戻る