최대공약수, 최소공배수 구하기

안녕하세요. KataRN입니다.

 

오늘은 최대공약수와 최소 공배수에 대해 알아보겠습니다.

 

최대공약수와 최소공배수에 대한 문제를 풀기 위해 코드를 작성했으나 전부 시간초과가 났습니다.

이건 답은 같아도 비효율적이기 때문입니다.

그래서 제가 내린 결론은 무조건 '유클리드 호제법을 이용하여 만들어야한다' 입니다.

 

유클리드 호제법이란?

유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

 

최대공약수, 최소공배수 코드(swift)

//최대공약수
func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        return gcd(b, a%b)
    }
}

//최소공배수
func lcm(_ n: Int, _ m: Int, _ gcd: Int) -> Int {
    return m*n / gcd
}

 

위의 코드를 이용하면 코드의 성능과 가독성을 높일 수 있습니다.

읽어주셔서 감사합니다.