4
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\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
    May 20 '13 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
    May 20 '13 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
    May 20 '13 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
    May 20 '13 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
    May 20 '13 at 22:19
3
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ could you please elaborate? \$\endgroup\$
    – Malachi
    Jan 2 '14 at 22:08
  • 1
    \$\begingroup\$ Why not (1..20).inject(:lcm)? \$\endgroup\$ Jan 3 '14 at 8:08
  • \$\begingroup\$ Ofcourse you can use range. \$\endgroup\$
    – Gorev-V
    Jan 3 '14 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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