유클리드 호제법을 몰랐기 때문에
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)
