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.

• TCSGrad: 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
• tokland: @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.
• TCSGrad: 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 :)
• TCSGrad: I'm glad you edited the answer - the final paragraph is the kind of feedback I was hoping for!
• steenslag: require 'prime' enables Prime.each(20) do |i|;flag = true;#etc. No need to implement prime? (11.prime? works) or primes_upto.

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)

• Malachi: could you please elaborate?
• 200_success: Why not (1..20).inject(:lcm)?
• Gorev-V: Ofcourse you can use range.