Swift - 최대공약수 (GCD)

최대 공약수 GCD (최소 공배수 LCM)

 

최대 공약수를 구하는 공식은 유클리드 호제법 을 이용하면 쉽게 구해집니다.

 

뺄샘을 이용해서 구하는 방법과 나눗셈을 해서 나오는 나머지 값으로 구하는 방법이 있습니다.

 

프로그래밍에서는 나눗셈을 이용해야 수가 큰수 일때도 성능이 떨어지지 않으므로 나눗셈을 이용한 방법을 진행할게요.

 

 

정수 A와 B값이 주어지면 A값을 B로 나눈 나머지값이 0일때까지 루프를 도는 재귀함수 방법으로 구하는 방식입니다.

# a값을 b값으로 나누어 나머지가 0이 될때까지 순환루프를 도는 방식입니다.

func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    } else {
        return gcd(b, a%b)
    }
}

먼저 정수 A, B값이 주어지면 B의 값이 0인지 판별을 해서 0이라면 A값을 리턴 해줍니다.

아닐 경우에는 다시 재귀함수를 실행하여 A파라미터로 B의 값을 , B의 파라미터에는 A%B의 나눈 나머지 값을 전달해서

0이 될때가지 전달하는 방법입니다.

  

설명으로는 이해가 힘들 수 있어 아래 로그를 참고해주시면 될 것 같아요.

gcd(20, 16)

--> a=20, b16
--> a=16, b4
--> a=4, b0

result = 4

 

반대로 큰값을 뒤에 넣어서 실행해 보겠습니다.

gcd(20, 16)

--> a=16, b20
--> a=20, b16
--> a=16, b4
--> a=4, b0

result = 4

 

이번에는 암산으로 계산 하기 힘든 정수를 실행해 보겠습니다.

gcd(52, 91)

--> a=52, b91
--> a=91, b52
--> a=52, b39
--> a=39, b13
--> a=13, b0

result = 13