Joseph Jude

Technology, Psychology, and Story Telling

Solving Euler-005 in Swift

Posted: Tags: code,euler,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 learnt 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 learnt. 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.


Comments

comments powered by Disqus