Problem 7

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

10001 番目の素数を求めよ。

Problem 7 - PukiWiki

Ruby

def prime?(n)
  (2..Math.sqrt(n)).each do |i|
    return FALSE if n%i == 0
  end
  return TRUE
end


c = 0
k = 1

while c < 10001 do
  k += 1
  c += 1 if prime?(k)
end

puts k

全然最適化とかしてなくてむしろ遅くなる感じに書いた。それでもこれくらいならすぐ計算できるもんなんですね。

R

is.prime <- function(n) {
  i <- 2
  while(i*i <= n) {
    if(n%%i == 0) {
      return(FALSE)
    }
    i <- i+1
  }
  return(TRUE)
}

c <- 0
k <- 1

while(c < 10001) {
  k <- k+1
  if(is.prime(k)) {
    c <- c+1
  }
}

print(k)

なんか遅い…

% time R -q --vanilla < 007.r
R -q --vanilla < 007.r  19.96s user 0.15s system 99% cpu 20.110 total
% time ruby 007.rb
ruby 007.rb  4.34s user 0.01s system 99% cpu 4.350 total

(´・ω・｀)

Haskell

main = print $ last $ primes [] [2..]
    where
      primes p (x:xs)
          | (length p) == 10001 = p
          | otherwise = primes (p++[x]) [y|y<-xs, (mod y x)/=0]

折角無限リストが使えるので調子乗って篩いっぽく書いたらすげー遅くなった…26秒…
最適化オプションをつけたら早くなる…なんて事は全然なかったぜ！！