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 }

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

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
      flag = false
  if flag
    lcm *= i
    range.map! {|y| y % i == 0? y/i : y}
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!)


2 Answers 2


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 }

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

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)

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

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.

  • \$\begingroup\$ 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 \$\endgroup\$
    – TCSGrad
    Commented May 20, 2013 at 1:47
  • \$\begingroup\$ @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. \$\endgroup\$
    – tokland
    Commented May 20, 2013 at 7:54
  • \$\begingroup\$ 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 :) \$\endgroup\$
    – TCSGrad
    Commented May 20, 2013 at 15:41
  • \$\begingroup\$ I'm glad you edited the answer - the final paragraph is the kind of feedback I was hoping for! \$\endgroup\$
    – TCSGrad
    Commented May 20, 2013 at 15:42
  • \$\begingroup\$ require 'prime' enables Prime.each(20) do |i|;flag = true;#etc. No need to implement prime? (11.prime? works) or primes_upto. \$\endgroup\$
    – steenslag
    Commented May 20, 2013 at 22:19

In Ruby, you can use this magic:


puts ns.inject(:lcm)
  • \$\begingroup\$ could you please elaborate? \$\endgroup\$
    – Malachi
    Commented Jan 2, 2014 at 22:08
  • 1
    \$\begingroup\$ Why not (1..20).inject(:lcm)? \$\endgroup\$ Commented Jan 3, 2014 at 8:08
  • \$\begingroup\$ Ofcourse you can use range. \$\endgroup\$
    – Gorev-V
    Commented Jan 3, 2014 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.