Swift - 백준 2609번 최대공약수와 최소공배수

최대공약수와 최소공배수는 공식을 통해 구할 수 있습니다

 

최대공약수

최대공약수는 다음과 같이 유클리드 호제법을 사용하면 쉽게 구할 수 있습니다.

• a와 b를 담습니다
• a에는 b의 값을 넣습니다
• b에는 a와 b의 나머지 값을 넣습니다
• b가 0이되는 순간 이전 b의 값 즉 a의 값이 최대공약수가 됩니다

 

150과 108의 최대공약수를 예시로 풀어보겠습니다.

1. 150 % 108 = 42

2. 108 % 42 = 24

3. 42 % 24 - 18

4. 24 % 18 = 6

5. 18 % 6 = 0

func GCD(a: Int, b: Int) -> Int {
    var a = a
    var b = b
    while b != 0 {
        let tmp = a % b
        a = b
        b = tmp
    }
    return a
}

 

최소공배수

최소공배수는 다음과 같이 함수로 만들어 구할 수 있습니다.

• 두 수를 곱한다
• 곱한 값을 최대공약수와 나눈다

func LCM(a: Int, b: Int) -> Int {
    return a * b / GCD(a: a, b: b)
}