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

• MTarantini: What is the goal here? The variable test doesn't seem to be used, nor is there a purpose for z.
• tristan: @MTarantini The goal is to improve performance on the script, as it takes quite a while to run. I got rid of variables.
• MTarantini: Well of course the goal here is to improve performance, that's why you posted it ;-) I meant what is the purpose of the script, not your post.
• tristan: @MTarantini Well I misread that... The goal is o find the smallest possible number than can be divided by numbers 1 to 20 without a remainder.
• tokland: Check codereview.stackexchange.com/questions/26346/…

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.

• MTarantini: I'm afraid the speed difference is significant, the original conditional is considerably faster. I benchmarked the original at: 3.981697, while the benchmark with the all method: 33.40386

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.