Project Euler Problem 7

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。

10001 番目の素数を求めよ。

もう問題は日本語訳でいいや．この問題は結局，今まで避けてきた素数列が必要となるのでそれをつくることを考える．とりあえず素数でないかのチェックをする方法を単純に倍数を取り除いていく方法を考える．いろいろ調べてみるとその方法にはエラトステネスの篩という由緒正しい名前がついているようだった．ということで「R エラトステネスの篩」とググると（おい），すばらしいページを発見．でパクリ，答えが出ました．なるほど，こうやって書くのか．人のコードを見ると勉強になるなぁ．完全にコピペなので問題があればご連絡ください．

eratosthenes <- function(x){
    x_0 <- (x-1)/2
    d <- rep(TRUE, x_0) #3,5,7,9... が素数かどうか
    l <- (sqrt(x) - 1) / 2
    p <- 1
    w <- 5 #which を行う範囲
    while (p < l) {
        step <- p * 2 + 1
        d[seq(p+step, x_0, step)] <- FALSE
        while(is.na(tmp <- which(d[(p+1):(p+w+1)])[1] + p)) {
            w <- w * 2 #whichの範囲内にtrue がないときは，which の範囲を2倍にする
        }
        p <- tmp
    }
    c(2,seq(3,x,2)[d])
}
prime <- eratosthenes(1000000)
prime[10001]