# Lowest Common Multiple of 1 to n in Ruby

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!)

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.

• I seem to be getting the following error in Ruby 1.8, when running the last line in irb: >> (1..20).reduce(:lcm) NoMethodError: undefined method lcm' for 1:Fixnum from (irb):1:in reduce' from (irb):1:in each' from (irb):1:in reduce' from (irb):1 May 20 '13 at 1:47
• @TCSGrad. This method was added in Ruby 1.9. Are you using 1.8 for some reason? it's ancient... anyway, I'll add an implementation to the answer. May 20 '13 at 7:54
• I have the second edition of the Pickaxe book, which covers Ruby 1.8 - in addition, the default version of the Ruby in my system is 1.8 - so, didn't bother upgrading both of them :) May 20 '13 at 15:41
• I'm glad you edited the answer - the final paragraph is the kind of feedback I was hoping for! May 20 '13 at 15:42
• require 'prime' enables Prime.each(20) do |i|;flag = true;#etc. No need to implement prime? (11.prime? works) or primes_upto. May 20 '13 at 22:19

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)

• Why not (1..20).inject(:lcm)? Jan 3 '14 at 8:08