Solving Euler-005 in Swift

I'm enjoying solving problems in Euler’s repository, though I’m only at the 5th problem. Why? Because I’m learning something new every time. Take this particular 5th problem. I learned that there are many different methods to solve this problem with varying performance. I also know now that the school algebra lessons are indeed useful!

Let me share what I learned. The problem statement is: Find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20. It sounds deceptively simple.

The first algorithm that I thought of is to start from 3, and find out if it is divisible by all numbers from 1 to 20 (i.e, reminder is 0, which means a % b == 0). If so, stop, else increment to the next number and repeat. This logic translates in Swift like this:

var divisor = 2 //start with 2, as all numbers are divisible by 1
var result = 3

while true {
if result % divisor == 0 {
divisor = divisor + 1
if divisor > 20 {
break
}
} else {
result = result + 1
divisor = 2
}
}

print(result)

It takes about 5000 milliseconds (5 seconds) on my MacBook Pro and gives me the correct result as 232792560. I can’t execute this in IBM swift playground because it takes more than 5 seconds. Hmm… Can I improve it?

When I thought about it, I don’t have to start from 3 because none of the numbers between 3 - 20 is evenly divisible by 20. I can start at 20. With the same logic, I don’t have to increment by 1; I can increment by 20. With this logic change the code becomes little better. I also separated the logic to test for divisibility.

func isDivisableBy2To20(number: Int) -> Bool {
for index in (2...20) {
if number % index != 0 {
return false
}
}
return true
}

result = 20
while true {
if isDivisableBy2To20(result) {
print(result)
break
} else {
result = result + 20
}
}

This modified code executes in 531 ms. That’s one hell of an improvement from 5000 ms!

Can I still improve it? Looks like I can. Little bit of search leads to school algebra. Remember GCD & LCM? Let me modify the code again.

func gcd(firstNumber: Int, _ secondNumber: Int) -> Int {
var a = firstNumber
var b = secondNumber
var t = 0
while b != 0 {
t = b
b = a % b
a = t
}
return a
}

result = 2
for index in (2...20){
result = index / gcd(result,index) * result
}
print(result)

This executes in 0.0059 ms. You can check it out at Swift Playground.

5000 to 500 to .0059 ms. That’s what a good algorithm does.

Got comments? Tweet it, or comment below.

Published On:
Under: #code , #euler , #swift