Project Euler, 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?

This one needed some rambling thought before I settled down to an approach. I had thought that there should be a more effective method than simply counting upwards while testing each number in the range.

I settled on the simple approach when I realised that when checking the current highest number, you can skip all remaining items in the range should there be a single failure to evenly divide.

My brief, if inelegant solution – which I’ll hopefully refine in the next few days – is copied below (written in Ruby). I can’t help but think there are ways to:

  • cut down the number of division checks
  • increment the high number by greater degrees each time

So plenty still to examine with this one.

$greatestNumber = 1
def checkHigh()
  rangeLow = 1
  rangeHigh = 20
  i =  rangeHigh  
  singleNumbersNonRemainDivCount = 0
  while i >= rangeLow
    if ($greatestNumber % i)   > 0
        singleNumbersNonRemainDivCount=0
        $greatestNumber = $greatestNumber+1    
        i = rangeHigh      
    else
        singleNumbersNonRemainDivCount=singleNumbersNonRemainDivCount+1
        if singleNumbersNonRemainDivCount == rangeHigh
          puts "Highest number: #{$greatestNumber}"
          $greatestNumber   = $greatestNumber-1
        end
        i=i-1
    end
  end
end
checkHigh()

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>