エラトステネスのふるい(210n+k)

 投稿者:しばっち  投稿日:2021年11月 3日(水)18時09分16秒
  エラトステネスのふるい(210n+k)

FOR I=1 TO 10
   LET N=I*10^5
   PRINT N;"th prime ";NTHPRIME(N)
NEXT I
END

EXTERNAL  FUNCTION NTHPRIME(M) ! M>4
LET N=M*(LOG(M)+LOG(LOG(M)))
DIM P(N),A(48)
MAT READ A
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,113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209
FOR I=0 TO INT(SQR(N)/210)
   FOR J=1 TO 48
      IF I=0 AND J=1 THEN LET J=2
      LET K=210*I+A(J)
      FOR L=K*K TO N STEP K*2
         LET P(L)=1
      NEXT L
   NEXT  J
NEXT  I
LET COUNT=4 ! M>4
FOR I=0 TO INT(N/210)
   FOR J=1 TO 48
      IF I=0 AND J=1 THEN LET J=2
      LET K=210*I+A(J)
      IF P(K)=0 THEN
         LET COUNT=COUNT+1
         IF COUNT=M THEN
            LET NTHPRIME=K
            EXIT FUNCTION
         END IF
      END IF
   NEXT J
NEXT I
END FUNCTION
 

戻る