Project Euler problem 10 meets the sieve of Eratosthenes

| | Comments (0) | TrackBacks (0)

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.

Leave a comment


Type the characters you see in the picture above.

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