iOS) swift-GCD LGM 최대공약수 최소공배수

2 min readApr 13, 2021

알고리즘 문제를 풀면서 좀 많이 최대공약수와 최소공배수에 관한 문제가 나왔다.
이론은 알고있고 손으로 풀 수 있어서 문제 없을거라 생각했는데.. 어라.. 코드로는 어떻게 구해? 하고 결국 막혔다.

결론부터 보면 swift로 두 수의 최대공약수와 최소공배수를 구하는 로직은 아래와 같다.

//최소공배수(LCM)
func getLeastCommonMultiple(_ m: Int, _ n: Int) -> Int {
    return m * n / getGreatestCommonDivisor(m, n)
}//최대공약수(GCD)
func getGreatestCommonDivisor(_ m: Int, _ n: Int) -> Int {
    var a = 0
    var b = max(m, n)
    var r = min(m, n)
    while r != 0 {
        a = b
        b = r
        r = a % b
    }    return b
}

최대공약수는 *유클리드호제법을 구현한 것이고
* 유클리드호제법 : 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
최소공배수는 최대공약수와 최소공배수의 관계 공식을 이용하였다.

음… 배열로 들어오는 수들의 최대공약수는 아래의 스크린샷 참고! 허접하지만 돌아간다;;

iOS) swift-GCD LGM 최대공약수 최소공배수

Written by Hongjeongseob