Greatest Common Divisor

Euclid is trying to find the largest common divisor of two numbers: a and b.

Example

Input:

let a = 3
let b = 9

Expected value/output:

3

[collapse]
Hint

Recursively subtract the smaller number from the larger number until they become equal. Can you see why this works? Take a rectangle with lengths a and b. Whenever you do a subtraction from a and b, reduce the rectangle accordingly. Run this algorithm until you are left with a square (with length a = b).

[collapse]
Solution

let a = 3
let b = 9

func gcd(a:Int, b:Int) -> Int {
    if a == b {
        return a
    }
    else {
        if a > b {
            return gcd(a:a-b,b:b)
        }
        else {
            return gcd(a:a,b:b-a)
        }
    }
}

print(gcd(a:a, b:b))

[collapse]
1 Star2 Stars3 Stars4 Stars5 Stars (4 votes, average: 4.25 out of 5)
Loading...
Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)