Project Euler - Smallest multiple (Ruby)

Question

My code is very slow to run, and I am trying to find a way to make it more efficient. I know there must be a better way than to write each modulo operation.

The goal of the script is to find the smallest possible number than can be divided by numbers 1 to 20 without a remainder.

def divide
  (2..Float::INFINITY).each do |x|
      if x % 2 == 0 && x % 3 == 0 && x % 4 == 0 && x % 5 == 0 && x % 6 == 0 && x % 7 == 0 && x % 8 == 0 && x % 9 == 0 && x % 10 == 0 && x % 11 == 0 && x % 12 == 0 && x % 13 == 0 && x % 14 == 0 && x % 15 == 0 && x % 16 == 0 && x % 17 == 0 && x % 18 == 0 && x % 19 == 0 && x % 20 == 0
        print x
        break
      end
  end
end

divide

Answer 1

Array provides lcm() which gives you the least common multiple of two numbers. You can apply this to an entire array by applying it to each result as you go through it. This is what reduce does.

puts (1..20).reduce{|m,n| m.lcm(n)}

or even shorter:

puts (1..20).reduce(:lcm)

Because most of the calculations are done in the ruby implementation (e.g. C for MRI), this will be fast.

Answer 2

all

Your if can become:

if (2..20).all? {|d| x % d == 0}

To avoid repetition.

all returns at the first false so this should be as fast as yours.

Answer 3

I would start at 20 and increase the number by 20 each time it loops:

def divide
  (20..Float::INFINITY).step(20).each do |x|
    if x % 2 == 0 && x % 3 == 0 && x % 4 == 0 &&
      x % 5 == 0 && x % 6 == 0 && x % 7 == 0 &&
      x % 8 == 0 && x % 9 == 0 && x % 10 == 0 &&
      x % 11 == 0 && x % 12 == 0 && x % 13 == 0 &&
      x % 14 == 0 && x % 15 == 0 && x % 16 == 0 &&
      x % 17 == 0 && x % 18 == 0 && x % 19 == 0 && x % 20 == 0

      puts x
      break
    end
  end
end

puts divide

Since 20 is the smallest number it could possibly be, we start there, since we know that it has to be evenly divisible by 20, we can continue increasing the number by 20 until it finds the solution.

At first I tried replacing your large conditional with a loop that would go from 2 to 20, testing the remainder, but this was much slower than your conditional.