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

문제 링크

유클리드 호제법을 몰랐기 때문에

https://tech.lonpeach.com/2017/11/12/Euclidean-algorithm/
이 분의 설명을 보았다!

최대공약수 구하기

먼저 숫자 a, b가 있다 (이때 a>b이다)
a를 b로 나누는데, 이 때

• 나머지 r이 0이라면 : b가 a와 b의 최대공약수이다.
• 나머지 r이 0이 아니라면 : b를 r로 나눠준다.
  • b를 r로 나눈 나머지 r2가 0 이라면 : r이 a와 b의 최대공약수이다.
  • b를 r로 나는 나머지 r2가 0이 아니라면 : r을 r2로 나눠준다.

다음과 같은 과정을 나머지가 0이 될 때까지 계속 반복한다.

이것을 코드로 작성하면

var max = nums.max()!
var min = nums.min()!
var r = max%min

while r > 0 {
    max = min
    min = r
    r = max%min
}

다음과 같다.

최소공배수 구하기

최소공배수는 최대공약수를 이용해서 간단하게 알 수 있다.

두 수 a,b가 있고 최대공약수를 G라고 할 때
a = Gx, b = Gy 이므로
a와 b의 최소공배수는 a*b/G이다

최종 코드

import Foundation

let nums = readLine()!.split(separator: " ").map{Int(String($0))!}

var max = nums.max()!
var min = nums.min()!
var r = max%min

while r > 0 {
    max = min
    min = r
    r = max%min
}

print(min)
print(nums[0]*nums[1]/min)