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.

## No comments:

Post a Comment