06 Feb 09 Project Euler: Problem 7 in Ruby

It took a couple hours of a couple days for me to come up with the solution to Problem #7, heck of a time. Looking over it now, the solution seems laughably obvious to me given the problems leading up to it. I'm going to optimistically take this as a sign that I'm learning...or something.

When I first began the problem I spent a lot of time trying to wheel and sieve my data set while totally ignoring my redundant method of testing primality!. Now I'm actually utilizing the data I'd already computed to help me speed up my algorithm at the piddly expense of storing a couple thousand integers.

NOTE: I realize that it isn't actually necessary to store all 10,001 numbers, but it's my program and I'll do what I want!

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 10001^(st) prime number?

target = 10001
stack  = [2,3]
n      = 1
 
def is_prime stack, n
  max_check = Math.sqrt(n).floor
  stack.each do |i|
    if i > max_check
      return true
    end
    if n % i == 0
      return false
    end
  end
  true
end
 
while true do
 
  if is_prime stack, n += 4
    stack << n
  end
 
  if is_prime stack, n += 2
    stack << n
  end
 
  if stack.length >= target
    break
  end
end
 
puts stack[target - 1]