ror dev newb ror dev newb - 4 months ago 16
Ruby Question

Ruby. How to improve my loop that searches for the smallest multiple of ranges of numbers

I need to deal with this task:

"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?"

My solution looks like this:

all_numbers = []

1.upto(2600) do |j|
1.upto(10) do |i|
if j % i == 0
all_numbers << j
end
end
end

result = all_numbers.select{|element| all_numbers.count(element) > 9 }
p result[0]


This gives me the right answer, but if I want to check for a range of
0..20
and change code like this:

all_numbers = []

1.upto(100000) do |j|
1.upto(20) do |i|
if j % i == 0
all_numbers << j
end
end
end

result = all_numbers.select{|element| all_numbers.count(element) > 19 }
p result[0]


it takes too much time to receive an answer (actually, I didn't even waited so long... So don't have the right answer yet..).

Any ideas? Many thanks!

Answer

You're attacking this from the wrong angle. Instead of searching until you find the right number, you want to calculate the number. Which basically means looking at all your numbers that the result needs to be divisible by, finding their prime factors, and then using the largest power of each prime. For example, finding the first number that is evenly divisible by the numbers 1-6 would be like this:

1: ignore
2: prime factors 2**1
3: prime factors 3**1
4: prime factors 2**2
5: prime factors 5**1
6: prime factors 2**1, 3**1

So, your unique primes are 2, 3, and 5. 2 is squared, everything else is to the first power. multiply that all together, and you get 2 * 2 * 3 * 5, which is 60. Taking it a teeny bit further for your 1-10 case, we have:

7: prime factors 7**1
8: prime factors 2**3
9: prime factors 3**2
10: prime factors 2**1, 5**1

So now your unique primes to their largest power are 2**3, 3**2, 5**1, 7**1 Multiply 2 * 2 * 2 * 3 * 3 * 5 * 7, and you get 2520. Which you already knew. Using this approach on the numbers 1-20 will get you a result much faster than going to each number.

Ruby has a Prime number library if you're allowed to use that (assuming this is a HW assignment). Specifically the prime_division method will basically return the prime factors in a very helpful way for this particular problem.

Comments