[Swift 코테] 백준 2609 최대공약수와 최소공배수

---

최대공약수와 최소공배수를 구하는 문제에서는 최대공약수만 안다면 최소공배수는 쉽게 구할 수 있다.

1. 최대 공약수를 부르트포스 처럼 모든 수로 나누는 방법을 생각했지만 유클리드 호제법이라는 알고리즘이 있었다.

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
-출처: 위키백과(https://ko.wikipedia.org/wiki/유클리드_호제법)

   gcf = greatest common factor: 최대공약수

   즉 gcf(a, b) = gcf(b, a%b)라는 것이고, a%b == 0일 때 b가 최대공약수이다. 

   이러한 결론은 아래 유튜브 링크에서 이해하는 편을 추천합니다.

    - https://ko.wikipedia.org/wiki/유클리드_호제법

 

2. 최소공배수 = (숫자1 / 최대공약수) * (숫자2 / 최대공약수) * 최대공약수

                      = 숫자1 * 숫자2 / 최대공약수

    예시) (24 / 6) * (18 / 6) * 6 = 4 * 3 * 6 = 72

 

 

 

 

---

//코드

import Foundation


//최대공약수 - 유클리드 호제법
func gcf(a: Int, b: Int) -> Int {
    if b == 0 {
        return a
    }
    return gcf(a: b, b: a % b)
}

let num = readLine()!.split(separator: " ").map { Int($0)!}
let div = gcf(a: num[0], b: num[1])

//최대공배수 = num1 * num2/최대공약수
let mul = num[0] * num[1] / div
print(div)
print(mul)