Project Euler Problem 7
問題
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^th prime is 13. What is the tex:10001^st prime number?
ソース
n = 10001 max = 150000 prime = Array.new(max, 1) prime[0] = 0 prime[1] = 0 i = 2 count = 1 while i <= max && count < n do (i + i).step(max, i) do |x| prime[x] = 0 end i = prime[(i + 1)..max].index(1) + i + 1 count += 1 end puts i
解答
104743
感想
「エラトステネスの篩」を知っていれば余裕かな
まぁ10001番目とか言われても、どこまで配列を用意すればいいのかがわからないので決め打ちになってしまうが。。。
答えが出るのに少し時間がかかるが、もう少し高速化できないものか。
追記
繰り返しの条件をsqrtしていないのは原因だとは分かっているが。。