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.
