Project Euler : Problem 7

Problem 7 is to “Find the 10,001^st prime.”

Here’s a brute force approach in Ruby:

def primes(n)
  primes = [2]
  i = 3
  until primes.length >= n
    primes << i unless primes.any? { |p| i % p == 0 }
    i += 2
  end
  primes
end

# What is the 10,001st prime?
puts primes(10001)[10001-1]

I’m running Ruby 1.9.1 RC1, and on my 2.2GHz Core2Duo MacBook, here are the timed execution results (I’ve masked the result so you can try it yourself):

davidkellis$ time ruby Projects/ruby/primes.rb 
######

real	0m9.125s
user	0m9.066s
sys	0m0.035s

I bet a C implementation would run in less than two seconds.