알고리즘 - 유클리드호제법[Swift](최대공약수)

최대 공약수

최대 공약수를 구하기 위해 매우 쉬운 공식인 유클리드 호제법은 에우클라이데스라는 그리스의 수학자가 만든 호제법이다.

 

계산 과정

648, 232 라는 수를 a % b = r을 가지고 계산해나간다.

큰 수가 a, 작은수가 b 가 되며, a를 b로 나눈 나머지가 r이된다

계산을 마치면  b -> a // r -> b 가 된다

648 % 232 = 184

232 % 184 = 48

184 % 48 = 40

48 % 40 = 8

40 % 8 = 0

8 % 0 = 0

조건은 b가  0이 아닌 동안이니 b가 0이 되었으므로 a를 return  한다.

소스코드

func GDC(_ num1: Int, _ num2: Int) -> Int{
    var a = num1 > num2 ? num1 : num2
    var b = num1 > num2 ? num2 : num1
    var r = 0
    while b != 0{
        r = a % b
        a = b
        b = r
    }
    
    return a
}