CODEWITHSUNDEEP
rubyoptimization
ntdef
ntdef

Reputation: 504

Slow Ruby computation? Project Euler #5

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?

Upvotes: 2

Views: 1803

Answers (5)

Raza Hussain
Raza Hussain

Reputation: 762

Simplest and clean solution in ruby language.

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

Upvotes: 1

Car
Car

Reputation: 387

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.

Upvotes: 1

Zach Latta
Zach Latta

Reputation: 3331

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)

Upvotes: 2

csharpbd
csharpbd

Reputation: 4066

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

Upvotes: 0

hammar
hammar

Reputation: 139850

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.

Upvotes: 3

Related Questions