How to find GCD of two numbers ?

[Question]: There is two number find the Greatest common divisor example 3,6 – GCD is 3
Better Approach using Euclidean algorithm Here we used recursion which swap the params with second argument as modulo divisor.

func gcd(_ a: Int, _ b: Int) -> Int {
    if (b == 0) { return a }
    return gcd(b, a % b)
}
print("GCD is-->", gcd(3, 11))//prints 1 because not found
print("GCD is-->", gcd(3, 6))//prints 3

If we do dry run for above code snippet
Case 1: For 3,11 a & b values in loop will be —
3 ,11
11, 3
3, 2
2, 1
1, 0 Here “b” is zero Hence returns 1 which is “a”
————————————————————————————————————————————————————————
Case 2: For 3,6 a & b values in loop will be —
3,6
6,3
3,0 Here “b” is zero Hence returns 3 which is “a”

Leave a Comment

Your email address will not be published. Required fields are marked *