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

Today 12/29

최대공약수와 최소공배수 (My Code)

var num = readLine()!.split(separator: " ").map{Int(String($0))!}
var GCD = 1

for index in stride(from: num.min()!, through: 2, by: -1) {
    if num[0] % index == 0 && num[1] % index == 0 {
        GCF = index
        break
    }
}
num[0] /= GCD
num[1] /= GCD
LCM = num[0] * num[1] * GCD
print(GCD, LCM, separator: "\n")

최대공약수 찾는 법을 몰라서 stride()로 뒤에서부터 하나씩 돌려봤다. 다행히도 최소공배수는 최대공약수를 통해 구했는데, 이상한 것 같아서 수정.

GCF로 두 번 나누고 한 번 곱할꺼면 애초에 한 번 나누는게 ... 바본가

또한 유클리드 호재법을 배우고 사용했다.

GCD(a, b) = GCD(b, r)

ex) GCD(581, 322) = GCD(322, 259) = GCD(259, 63) = GCD(63, 7) = GCD(7, 0) = 7

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
var num1 = input[0]
var num2 = input[1]

while num2 != 0 {
    let temp = num2
    num2 = num1 % num2
    num1 = temp
}
print(num1, input[0]*input[1]/num1, separator: "\n")