|
|
エラトステネスのふるい(2310n+k)
FOR I=1 TO 6
LET N=10^I
PRINT N;"th prime";NTHPRIME(N)
NEXT I
END
EXTERNAL FUNCTION NTHPRIME(N)
LET SIZE=10000000
DIM P(SIZE),A(480)
MAT READ A
DATA 1, 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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229, 233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293, 299, 307, 311, 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367, 373, 377, 379, 383
DATA 389, 391, 397, 401, 403, 409, 419, 421, 431, 433, 437, 439, 443, 449, 457, 461, 463, 467, 479, 481, 487, 491, 493, 499, 503, 509, 521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617, 619, 629, 631, 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701, 703, 709, 713, 719, 727, 731, 733, 739, 743, 751, 757, 761, 767, 769
DATA 773, 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827, 829, 839, 841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901, 907, 911, 919, 923, 929, 937, 941, 943, 947, 949, 953, 961, 967, 971, 977, 983, 989, 991, 997,1003,1007,1009,1013,1019,1021,1027,1031,1033,1037,1039,1049,1051,1061,1063,1069,1073,1079,1081,1087,1091,1093,1097,1103,1109,1117,1121,1123,1129,1139,1147,1151,1153
DATA 1157,1159,1163,1171,1181,1187,1189,1193,1201,1207,1213,1217,1219,1223,1229,1231,1237,1241,1247,1249,1259,1261,1271,1273,1277,1279,1283,1289,1291,1297,1301,1303,1307,1313,1319,1321,1327,1333,1339,1343,1349,1357,1361,1363,1367,1369,1373,1381,1387,1391,1399,1403,1409,1411,1417,1423,1427,1429,1433,1439,1447,1451,1453,1457,1459,1469,1471,1481,1483,1487,1489,1493,1499,1501,1511,1513,1517,1523,1531,1537
DATA 1541,1543,1549,1553,1559,1567,1571,1577,1579,1583,1591,1597,1601,1607,1609,1613,1619,1621,1627,1633,1637,1643,1649,1651,1657,1663,1667,1669,1679,1681,1691,1693,1697,1699,1703,1709,1711,1717,1721,1723,1733,1739,1741,1747,1751,1753,1759,1763,1769,1777,1781,1783,1787,1789,1801,1807,1811,1817,1819,1823,1829,1831,1843,1847,1849,1853,1861,1867,1871,1873,1877,1879,1889,1891,1901,1907,1909,1913,1919,1921
DATA 1927,1931,1933,1937,1943,1949,1951,1957,1961,1963,1973,1979,1987,1993,1997,1999,2003,2011,2017,2021,2027,2029,2033,2039,2041,2047,2053,2059,2063,2069,2071,2077,2081,2083,2087,2089,2099,2111,2113,2117,2119,2129,2131,2137,2141,2143,2147,2153,2159,2161,2171,2173,2179,2183,2197,2201,2203,2207,2209,2213,2221,2227,2231,2237,2239,2243,2249,2251,2257,2263,2267,2269,2273,2279,2281,2287,2291,2293,2297,2309
LET T=0
DO
LET S=T*SIZE
LET E=(T+1)*SIZE
MAT P=ZER
FOR I=0 TO INT(SQR(E)/2310)
FOR J=1 TO 480
IF I=0 AND J=1 THEN LET J=2
LET K=2310*I+A(J)
LET KK=INT(S/K)*K
IF KK=0 THEN LET KK=K*K
IF KK < S THEN LET KK=KK+K
IF MOD(KK,K)<>0 THEN LET KK=KK+K
IF MOD(INT(KK/K),2)=0 THEN LET KK=KK+K
FOR L=KK TO E STEP K*2
LET P(L-S)=1
NEXT L
NEXT J
NEXT I
LET COUNT=0
IF S<=11 THEN LET COUNT=1
IF S<=7 THEN LET COUNT=2
IF S<=5 THEN LET COUNT=3
IF S<=3 THEN LET COUNT=4
IF S<=2 THEN LET COUNT=5
FOR I=INT(S/2310) TO INT(E/2310)
FOR J=1 TO 480
IF I=0 AND J=1 THEN LET J=2
LET K=2310*I+A(J)
IF K>E THEN EXIT FOR
IF K>=S AND P(K-S)=0 THEN
LET COUNT=COUNT+1
IF TOTAL+COUNT>=N THEN
LET NTHPRIME=K
EXIT FUNCTION
END IF
END IF
NEXT J
NEXT I
LET TOTAL=TOTAL+COUNT
LET T=T+1
LOOP
END FUNCTION
|
|