[C language] [Swift] 알고리즘 | 재귀함수 (GCD 최대공약수)

최대공약수. greatest common divisor.

최대공약수가 뭔지는 다들 알고 있을 것이다.

 

우선 C로 구현한것.

1. 이것을 원칙대로 푼다면, 각 수의 공약수를 먼저 구하고, 그 공약수들이 서로 일치하는지, 그리고 그것이 최대인지 판별해야 한다.

코드로 구현해보면..

내 머릿속으로 생각한 가장... 간결하게 만든 코드...

그렇지만 이것저것 해야 하는것들이 많다. 작은 수도 봐야 하고, 두개가 모두 나누어 떨어지는지도 봐야 하고.

 

그리고 찾아보니까

너무 어이없게 짧은데 되는거같은 코드..

2. 삼항연산자를 이용했다.

 

3. 유클리드 호제법 이라고 최대공약수를 간단하게 구할 수 있는 방법이 있다고 한다.

재귀호출로 구현했다.

for문으로 구현했다.

 

최대공배수도 구할 수 있다.

두 수를 곱하고, 최대공약수로 나누면 최대공배수이다.

lcm(최소공배수) = (a * b) / gcd(a,b)

그러니.. 굳이 구현하진 않겠다.

 

그리고 Swift를 연습하기 위해

 

유클리드호제법을 이용한 gcd를 Swift로 구현한 코드.

아 이젠 귀찮아..

 

 

유클리드 호제법에 관한 설명. : 

ko.wikipedia.org/wiki/유클리드_호제법

유클리드 호제법 - 위키백과, 우리 모두의 백과사전