エラトステネスの篩 - the Sieve of Eratosthenes

This is a post written in RMarkdown (*.Rmd) to visualize the Sieve of Eratosthenes.

この記事ではチャートやグラフに対数目盛りを使う目的についてまとめています。Naomi Robbins¹さん、The Sieve of Eratosthenes in R²を参考にしています。

キーポイント

素数とは何だろう？:

2以上の整数で、1と自分自身の数以外では割ることのできない数
2は一番小さい素数である。素数の数は無限にある。³

エラトステネスの篩の手順⁴:

2以上の整数を昇順で並べたリストを作る。n:(2,3,4,..,n)
初めにpを2とする。（一番小さな素数）
pからnまで、p以外のpの倍数をリストから篩い落として行く。(2x2, 2x3, 2x4, 2x5,..)
nの平方根になる最初の値を見つけるまで篩い落として行く。

これを1単位ずつ繰り返す。(2p,3p,4p…)

# The Sieve of Eratosthenes

# Given a number greater than zero this function will return
# a list of primes between 2 and the number given as
# argument.
sieveOfEratosthenes <- function(num) {
    values <- rep(TRUE, num)
    values[1] <- FALSE
    prev.prime <- 2
    for (i in prev.prime:sqrt(num)) {
        values[seq.int(2 * prev.prime, num, prev.prime)] <- FALSE
        prev.prime <- prev.prime + min(which(values[(prev.prime + 
            1):num]))
    }
    return(which(values))
}

sieveOfEratosthenes(2000)

##   [1]    2    3    5    7   11   13   17   19   23   29   31   37   41   43
##  [15]   47   53   59   61   67   71   73   79   83   89   97  101  103  107
##  [29]  109  113  127  131  137  139  149  151  157  163  167  173  179  181
##  [43]  191  193  197  199  211  223  227  229  233  239  241  251  257  263
##  [57]  269  271  277  281  283  293  307  311  313  317  331  337  347  349
##  [71]  353  359  367  373  379  383  389  397  401  409  419  421  431  433
##  [85]  439  443  449  457  461  463  467  479  487  491  499  503  509  521
##  [99]  523  541  547  557  563  569  571  577  587  593  599  601  607  613
## [113]  617  619  631  641  643  647  653  659  661  673  677  683  691  701
## [127]  709  719  727  733  739  743  751  757  761  769  773  787  797  809
## [141]  811  821  823  827  829  839  853  857  859  863  877  881  883  887
## [155]  907  911  919  929  937  941  947  953  967  971  977  983  991  997
## [169] 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091
## [183] 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193
## [197] 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291
## [211] 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423
## [225] 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493
## [239] 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601
## [253] 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699
## [267] 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811
## [281] 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931
## [295] 1933 1949 1951 1973 1979 1987 1993 1997 1999

length(sieveOfEratosthenes(2000))  # 303

## [1] 303

ベイカー・ストリート

ベイカー・ストリート

エラトステネスの篩 - the Sieve of Eratosthenes

キーポイント