Prudent Devs

Solving Euler-005 in Swift

Know your algorithms

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.

Git Repository / All Euler Solutions

Got comments? Tweet it, or comment below.

Published On:
Under: #code , #euler , #swift
Sign up for my newsletter