Slow Ruby computation? Project Euler #5

Question

This question references Project Euler Problem 5, so beware of spoilers! Problem 5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I wrote the following code in Ruby as a solution to Problem 5.

num = 2520
until (1..20).all?{|x| num % x == 0}
  num += 1
end
puts "#{num}"

However, whenever I run the script, it just hangs. Note that I tested the same method on the base case 2520 for the range 1 to 10 and it worked just fine.

Why does it work for the simpler case but not for the more advanced case? What can I do to fix what I have?

"However, whenever I run the script, it just hangs." That's odd, it ran in two minutes and six seconds here. Considering that some people have let their programme run for several days to get the answer for some later questions, that's not too bad for a naive brute force. — Daniel Fischer, May 29 '13 at 14:34
That's telling! I guess I just got impatient because I just '' out after a few seconds. I should have let the script run longer. — ntdef, May 29 '13 at 17:38
related: [Least common multiple for 3 or more numbers](http://stackoverflow.com/a/147539/4279) — jfs, Feb 19 '14 at 06:53

hammar · Answer 1 · 2013-05-29T04:51:19.807

3

It's slow because the answer is more than 200 million, and you're counting up to it in steps of 1. That's going to take a while. You need a better algorithm.

edited May 29 '13 at 04:51

answered May 29 '13 at 04:44

hammar

138,522
17
304
385

I didn't really know in what ballpark the answer was going to land, so that helps. Do you have any suggestions? – ntdef May 29 '13 at 04:45
@freshfruit: Hint: [Least common multiple](http://en.wikipedia.org/wiki/Least_common_multiple). – hammar May 29 '13 at 04:47

Zach Latta · Accepted Answer · 2013-06-03T08:12:01.930

2

You won't be able to brute force this problem as you have with others. You're going to need to find a more efficient solution for it.

SPOILER BELOW

This is a significantly more efficient way to do it (apologies if this isn't very Ruby-like):

def find_multiple
  lcm = 1

  (2..20).each do |i|
    lcm *= i / gcd(lcm, i)
  end

  lcm
end

def gcd(a, b)
  while b > 0
    a %= b
    return b if a == 0
    b %= a
  end

  a
end

puts find_multiple

If you're looking for a more Ruby-like way to solve it, you can use the following (as suggested by steenslag in the comments):

(1..20).inject(:lcm)

edited Jun 03 '13 at 08:12

answered May 29 '13 at 04:54

Zach Latta

3,251
5
26
40

1

So I was trying to compress the solution as much as possible, and the best answer I found from digging around was `require 'rational' puts (1..20).inject(1) { |result, n| result.lcm n }`, which is more ruby-like and impressively efficient. But +1 for a great answer! – ntdef May 29 '13 at 05:05
Although that does look much nicer, it's generally considered against the Project Euler spirit to use libraries. Additionally, the solution I provided generally runs in about `0.131000` seconds on my machine. The one in your comment runs in about `0.258000` seconds, which is almost twice as long. I'll add your revised solution to my answer because it does look much nicer and is much easier to understand. I'm glad I could help! – Zach Latta May 29 '13 at 06:24
2

Even shorter solution (Integer class already has lcm method): `(1..20).reduce{|l,i|l.lcm i}` – tkroman May 29 '13 at 08:13
3

@cdshines Same thing, but shorter: `(1..20).inject(:lcm)`. – steenslag May 29 '13 at 12:15
Ah, didn't realize. I'll change the answer now. – Zach Latta May 29 '13 at 14:21

score 1 · Answer 3 · answered Apr 07 '14 at 05:05

A little late to the game but here's my input. If you like your code - which is succinct and pretty clear - you can make a couple of small adjustments to make it run faster. This worked for me without timing out:

num = 20

  until (11..20).all?{ |i| num % i == 0 }
    num +=20
  end

puts num

Essentially you just increment by 20s since you know it needs to be divisible by 20, and you can skip iterating through anything in the lower 1/2 of the set.

score 1 · Answer 4 · answered Jan 29 '15 at 11:05

1

Simplest and clean solution in ruby language.

(1..20).inject(:lcm) # output will be 232792560

answered Jan 29 '15 at 11:05

Raza Hussain

762
8
18

score 0 · Answer 5 · answered May 29 '13 at 04:56

Try this. Code:

i=2520
max_product = (4..19).inject(1){|j,k| j*k}
puts max_product
while i < max_product
    if( [3, 7].inject(true) do |memo, p|
        memo && i%p==0
    end)
      if( 
          (4..20).inject(true) do |memo, p|
          memo && i%p==0
          end 
      )   
      puts i
      end 
    end 
    i+=10
end

Slow Ruby computation? Project Euler #5

5 Answers5

SPOILER BELOW