# 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? # Brute force: can check by 20 then downward from 20 for divisible / This takes a long time # Trick: the next multiplier is always a multiple of the prior multiplier require "benchmark" def smallestDivisibleValue(num) # num is the amount of results to generate resultArray = [1] # the first value is a given and preset index = 0 # index of the first array element multiplier = 1 # initialize the multiplier, used to determine the currentTestValue until value is found count = 2 # identifies the current position to be evaluated (starts off checking for the 2nd value) found = false # used to check whether a correct value is found while (true) currentTestValue = resultArray[index] * multiplier # currentTestValue is a multiple of the prior result (1..count).to_a.reverse.each do |i| if(currentTestValue % i === 0) # currentTestValue must be evenly divisible by all 'i' values to be 'found' found = true else found = false break # exit the loop in the event that the currentTestValue is not divisble end end multiplier += 1 # increment the multiplier by 1 if found === true resultArray.push(currentTestValue) multiplier = 1 # reset the multiplier back to 1, needs to happen after multiplier increment (prevent pre-increment) index += 1 # increment the index count += 1 end return resultArray if resultArray.length === num # saves the result into an array and returns the array when length is equal to user input number end end time = Benchmark.realtime do puts smallestDivisibleValue(20)[19] # the 19th index value is the 20th element in the area, thus the answer end puts "Time elasped #{time*1000} milliseconds" # output: # 232792560 # Time elasped 0.316 milliseconds