22-Oct-2013 by Allison McMillan

Read Time: Approx. 2 minutes

Halfway there. Euler 5.

Euler 5! Phew, so, this marked my halfway point through the 10 problems I decided to do in Project Euler.

So, here is the problem:

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?
For this problem, I actually solved it in a really ugly, awful way and then went back to refactor . I can't remember exactly but I think the ugly way involved taking a range of numbers, multiplying all of them and then seeing which was the smallest that had a remainder of 0 for each of the numbers... whatever it was, it was super complicated. Anyway, so first, the tests:

require 'problem5/problem5'
describe 'lowest common multiple' do
it "find the smallest number that can be divided by 1 through 10 with no remainder" do
expect(Problem5.divided_by(1...10)).to eq 2520

it "finds the smallest number that can be divided by 1 through 20 with no remainder" do
expect(Problem5.divided_by(1...20)).to eq 232792560

At this point, if you've been reading the Euler series of this blog, you'll notice a pattern to all of the tests. This may not be the most sophisticated way to execute the tests since rspec can do a lot of cool things, but using the same format worked for and was a way I became comfortable with seeing tests formats, running the tests, etc.

Now for the answer:
module Problem5

def self.divided_by(number_range)
list = (number_range).inject(:lcm)
return list

puts Problem5.divided_by(1..20)


so, once I started reading the ruby docs, I noticed there was a greatest common denominator and a least common multiple method with an integer. Looking into those, the least common multiple method was a perfect, simple way to solve this problem. The inject plus LCM method on an integer basically takes a list and finds the lowest common multiple of that range of numbers.

Ready to chat?

Join my mailing list

* indicates required

Set up a free call

phone icon