Project Euler problems 6 - 10

I finally found some time to sit down and do problems 6 through 10 on Project Euler.

Problem 6: Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

def euler6()
  (1..100).inject(0){|val,k| val += k} ** 2 -
  (1..100).inject(0){|val,k| val += k**2}
end

Problem 7: What is the 10001st prime number?

def euler7()
  myprime = Prime.new
  (1..10000).each{ myprime.next}
  myprime.next
end

Problem 8: Find the greatest product of five consecutive digits in the 1000-digit number.

The 1000 digit number is a string in my code.

def euler8(bigNum)
  len = bigNum.size
  stopAt = len - 5
  sliceStart = 0
  res = 0
  while sliceStart < stopAt do
      val = 1
      s = bigNum.slice(sliceStart, 5)
      s.each_char{|x| val *= x.to_i}
      res = val if res < val
      sliceStart += 1
  end
  res
end

Problem 9: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

def euler9()
  val = 0
  (1..500).each{ |a|
      (a..500).each{ |b|
          c = (a**2 + b**2)**0.5
          next unless c == c.to_i # continue unless c is an integer
          val = a + b + c
          return a * b * c if val == 1000
          break if val > 1000
      } 
  } 

end

Project 10: Find the sum of all the primes below two million.

This was the only really challenging problem in this set. I tried to use Ruby's Prime class in a loop for this. When ran for 50,000 iterations it would return in about 14 seconds. For 2,000,000 I eventually killed the process after 15 minutes. The algorithm used in the Prime class seems to fall down when used to generate large lists of prime numbers.

I did some searching and found that most people were using some type of number sieve to generate the list of prime numbers, see Wikipedia here and here. I found and shamelessly stole a Ruby implementation of the Sieve of Eratosthenes from Paul Callagher. I slightly modified Paul's implementation to make it a standalone function instead of a class method.

# problem 10, find the sum of all primes below 2,000,000.
# prime series up to this limit, using Sieve of Eratosthenes method
# http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#
# from http://tardate.blogspot.com/2008/10/rolling-project-euler-on-ruby.html
def sieve_of_eratosthenes( maxVal )
  limit = Math.sqrt(maxVal)                        
  a = (2..maxVal).to_a                             
  n = 2                                            
  while (n < limit) do                             
      x = n*2
      begin                                        
          a[x-2]=2                                 
          x+=n                                     
      end until (x > maxVal )
      begin
          n+=1
      end until ( a[n-2] != 2 )
  end
  a.uniq!
end

def euler10()
  sieve_of_eratosthenes( 2_000_000 ).inject(0){|val, x| val += x }
end

This code returns in about 4 seconds.