최대공약수와 최소공배수 Swift

최대공약수 GCD

두 자연수의 공통된 약수 중 가장 큰 수

ex) 30 과 45 의 최대공약수는 15

 

최소공배수 LCM

두 자연수의 공통된 배수 중 가장 작은 수

최소공배수 = 두 자연수의 곱 / 최대공약수

ex) 6과 10의 최소공배수는 30

 

 

유클리드 호제법

2개의 자연수 a,b에 대해 (a > b) a를 b로 나눈 나머지를 r이라 하면

a와 b의 최대공약수는 b와 r의 최대공약수와 같다

이 성질을 이용해,

b를 r로 나눈 나머지를 r0라 하고, r을 r0으로 나누는 과정을 반복해서 나머지가 0일때 

나눈수가 a와 b의 최대공약수가 된다. 

 

func gcd(num1: Int, num2: Int) -> Int {
    if num2 == 0 {
        return num1
    } else {
        return gcd(num1: num2, num2: num1 % num2)
    }
}

시간복잡도: O(logN)