Project Euler–Problem 5

Description

From Project Euler:

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

Another name for the smallest number that is evenly divisible by two or more numbers is the least common multiple (LCM). In general, finding the least common multiple is an easy task if we make the following observation. All numbers greater than 1 can be expressed uniquely as the product of its prime factors. 
10 => 2, 5 => 2 x 5
In addition, each prime factor may have an exponent greater than one.
90 => 2, 3, 3, 5 => 2¹ x 3² x 5¹
To find the least common multiple of two or more numbers, you take the prime factorization of each number, than multiply the highest exponent of each prime together. This gives the least common multiple. (For more information on how this works, see this Wikipedia article).
8 => 2, 2, 2    => 2³
18 => 2, 3, 3    => 2¹ x 3² 84 => 2, 2, 3, 7 => 2² x 3¹ x 7¹
lcm(8, 9, 21) => 2³ x 3² x 7¹ => 504
We already created a method that can compute the prime factors for us in problem 3. However, now, we don’t want to simply list them, we want to list the factors exactly once with their associated exponent. To do this, we’ll change the prime_factors method to instead return a hash. The keys of the hash will be the prime factors, and the values will be the exponent.

class Integer
 def prime_factors
  prime = 2
  result = {}
  value = self
  while value >= prime ** 2
   if value % prime == 0
    result.merge!(prime => 0) if not result.has_key?(prime)
    result[prime] += 1
    value /= prime
   else
    prime += 1
   end
  end
  result.merge!(value => 0) if not result.has_key?(value)
  result[value] += 1
  return result
 end
end

Note that this does force us to change the solution to problem 3:

600_851_475_143.prime_factors.keys.max

Only a minor change, we are now calling keys on prime_factors before calling max.
Now the method for computing the least common multiple becomes trivial:

class Problem005
 def lcm(*numbers)
  factors = {}
  numbers.each do |n|
   factors.merge!(n.prime_factors) do |key,x,y|
    x > y : x : y
   end
  end
  factors.inject(1) { |product,pair| product * (pair[0] ** pair[1]) }
 end
end
Problem005.new.lcm 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

The only thing to note here is that we are overriding the merge! methods logic. Instead of overwriting the current value of the hash with the new one, we always add the larger number to the hash. Thus, { 5 => 2}.merge( 5 => 1) would result in { 5 => 2 } instead of { 5 => 1 }.
The full source and specifications can be seen on github. Next time, the difference between the sum of squares and the square of sums.