24 Jan 09 Project Euler: Problem 5 in Ruby

I was stuck on this one for way too long. I was able to figure out a brute force approach quickly enough, but it was taking forever. Finally after hours (told you I took way too long!) of scratching around in my notebook before I had my eureka moment. I basically just determined that the least common multiple between 2 contiguous numbers must be a factor of my final result, and from there I just stepped my way up the chain. It's running in about 24ms on my machine!

I also determined that I didn't need to check any numbers under 1/2 of the given number 20 since they were already factors of the higher numbers, but that doesn't actually effect the Big O and the timing difference is negligible.

PS: Yes, I used the exact library that I accused Olathe and Mat of "cheating" for on Problem #4. Shush!

Problem #5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

 require 'mathn'
 
max = 20
min = (max / 2).floor + 1
n   = min
 
(min..max).each do |i|
  n = n.lcm i
end
 
puts n

I was pretty proud of this solution and given all the incarnations this program's been through I thought it came out really nice...until (you guessed it) I saw Olathes!

 require 'rational'
num = (1..20).inject(1) { |result, n| result.lcm n }
puts "Smallest evenly divisible number is #{ num }."

Tags: project euler, ruby