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

🔗 문제 링크

https://www.acmicpc.net/problem/2609

💡 문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

⌨️ 입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

🖨️ 출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

✅ 풀이

최대공약수

최대공약수를 구하는 방법에는 여러가지가 있겠지만 유클리드 호제법 이 가장 쉬운 방법 중 하나입니다.

두 자연수 a, b에 대해서 a를 b로 나눈 나머지가 r이라면 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.

더욱 쉽게 말하자면 위의 과정을 연속해 나머지가 0이 나올때 까지 나누면 그 수가 최대공약수 입니다.

최소공배수

최소공배수는 최대공약수 보다 더욱 구하기 쉽습니다.

두 수 a, b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수로 나눈 것 과 같습니다.

첫번째 방법

첫번째 방법은 최대공약수와 최소공배수를 구하는 함수를 따로 만들어 반환값을 출력하는 방법 을 선택했습니다.

최대공약수를 구할때 나머지가 0이 나올떄 까지 나눠야 하기 떄문에 재귀함수 로 구현을 하였습니다.

재귀함수로 구현해서 그런지 두번째 방법보다 시간이 더 오래걸렸습니다…..

두번째 방법

두번째 방법은 함수로 구현하지 않고 푸는 방법을 선택했습니다.

테스트 입력은 큰 수가 먼저 입력되지만 꼭 그런 경우는 없기 때문에 큰 수와 작은 수를 먼저 분리 했습니다.

그 다음 나머지가 0이 될때까지 반복문 을 통해 최대공약수를 구했고 최소공배수 또한 간단한 식으로 구했습니다.

다행히도 첫번째 방법보다 훨씬 단축되었습니다.

🖥️소스코드

첫번째 방법

func gcd(_ a : Int, _ b: Int) -> Int {
    let mod = a % b
    return mod == 0 ? min(a, b) : gcd(b, mod)
}

func lcm(_ a : Int, _ b: Int) -> Int {
    return (a * b) / gcd(a, b)
}

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

print(gcd(num[0], num[1]))
print(lcm(num[0], num[1]))

두번째 방법

let num = readLine()!.split(separator: " ").map{Int(String($0))!}
 
var a = max(num[0], num[1])
var b = min(num[0], num[1])
 
while a % b != 0 {
    let temp = a % b
    a = b
    b = temp
}
 
print(b)
print(num[0] * num[1] / b)