Lowest Common Multiple of 1 to n in Ruby

Question

Project Euler problem 5 asks:

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

I'm learning Ruby by going through Project Euler problems, and though I got the following code right (as in the answer given by it), I'm not sure if I'm doing things quite the "Ruby way". Hence, I wanted the community's opinion of my code to better understand alternatives to my code (using the same algorithm please!), so that I don't become used to writing "C++ using Ruby!"

def prime? x
  (2..x-1).each { |y| return false if x % y == 0 }
  true
end

def primes_upto n
   p = Array.new
   (2..n-1).each {|x| p.push(x) if prime? x}
   return p
end

upto = 20 # The upper limit of the LCM range
primes = primes_upto upto
range  = Array.new(upto) {|i| i + 1}
lcm = 1
primes.each do |i|
flag = true
while flag and range.length > 0
  range.each do |x|
    if x % i == 0
      flag = true
      break
    else
      flag = false
    end
  end
  if flag
    lcm *= i
    range.map! {|y| y % i == 0? y/i : y}
  end
  range.delete(1)
  range.compact!
end
end
print "\nLCM of 1..", upto, " = ", lcm

In particular, I would like to take advantage of ruby's built-in operators on Array, to reduce the size of the code, as well as make it less of an if-then, while structure that I've seen in C++ programs.

The algorithm I've used can be found here (if its not obvious from the code!)

Answer 1

Definitely your code looks like C directly translated to Ruby. Let's refactor the first two methods:

def prime?(n)
  (2..n-1).none? { |x| n % x == 0 }
end

def primes_upto(n)
  (2..n-1).select { |x| prime?(x) }
end

Of course prime? should be checking only 2 and odd numbers until sqrt(x) as candidates. Although you probably should be using the library in the core: Prime.

Calculating the lcd using a table is a possible way to do it, granted, but having the standard formula lcm(a, b) = a * b / gcd(a, b), and gcd being easily calculated with Euclides algorithm, well, I don't see why you'd choose that other way.

Anyway, note that to get the lcm of three numbers you can do lcm(a, b, c) = lcm(a, lcm(b, c)) (you get the idea for N numbers), and since Ruby >= 1.9 has Integer#lcm, you could simply write a left fold of the range:

(1..20).reduce(:lcm) #=> 232792560

BTW, that's how you could implement Integer#lcm in 1.8, a direct translation of the formulas:

class Integer
  def gcd(b)
    b == 0 ? self : b.gcd(self % b)
  end

  def lcm(b)
    (self * b) / self.gcd(b)    
  end
end

A final advice: project-euler is about maths. When doing maths you should try to use expressions (functional programming) instead of statements and change of state (imperative programming). Try to do these problems without any of these: each, var = some_initial_value, push, bang_methods!, break, return, *=, +=, delete, while, ... Instead, you should be using: map, select, reduce, detect, zip, any?, all?, flatten, take_while, lazy (Ruby 2.0)... More on functional programming with Ruby.

Answer 2

In Ruby, you can use this magic:

ns=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

puts ns.inject(:lcm)