Problem 10 of Project Euler is to sum the prime numbers less than two million. Solutions are supposed to take no more than one minute, so a decent prime number detector is mandatory. I'm sure lots of free, high quality solutions are available, but I have this problem with DIY / NIH syndrome. Somehow I found the sieve of Eratosthenes and a quick, tacky swipe at it was good enough.
This process is to make a list of numbers from 2 through some limit. Start with the lowest number in the list, and remove all multiples from the list. Next time through, pick the next smallest number that hasn't been crossed off yet and eliminate its multiples. Stop when your current number meets the square root of the limit. After that, the remaining numbers are prime:
def eratosthenes_sieve(ceiling)
vals = (0..ceiling).to_a
vals[0..1] = [nil, nil]
Math.sqrt(ceiling).floor.times do |val|
next unless vals[val]
((val ** 2)..ceiling).step(val) do |mult|
vals[mult] = nil
end
end
vals
end
A big hash like this is useful for O(1) checking for prime/not prime, but the solution requires the sum of the primes:
def primes_through(ceiling)
eratosthenes_sieve(ceiling).compact
end
sum = 0
primes_through(ARGV[0].to_i).each { |val| sum = sum + val }
puts sum
I'm sure there's a more Ruby-esque way to write that. I wanted to use Python for xrange goodness, but I'm still not at peace with its quirks. Groovy would have been nice, but the free editor support is still quite young. Ruby fit right in the gap.
0 TrackBacks
Listed below are links to blogs that reference this entry: Project Euler problem 10 meets the sieve of Eratosthenes.
TrackBack URL for this entry: http://www.nearinfinity.com/mt/mt-tb.cgi/495



Leave a comment