최대공약수 GCD 알고리즘. 유클리드.

GCD는 두 개 이상의 정수의 공통 약수 중 가장 큰  값을 의미

최대공약수 알고리즘

1. 4,6 중 작은 수인 4를 i에 저장
2. 4는 i로 나눠떨어지나 6은 아니다
3. i-1을 해서 3으로 만든다
4. i는 6과 나눠떨어지나 4은 아니다
5. i-1을 해서 2로 만든다
6. i는 4,6 모두와 나눠떨어지므로 2가 최대공약수이다.

def gcd(a,b) :
    i = min(a,b)
    while True : 
        if a % i == 0 and b % i == 0 :
            return i 
        i -=1

유클리드 알고리즘

유클리드가 발견한 GCD성질을 이용한 알고리즘!
유클리드가 발견한 것은 다음과 같다

1. a,b의 GCD는 'b' 와 'a를 b로 나눈 나머지'의 최대공약수와 같다.
   즉, gcd(a,b) = gcd(b, a%b)
2. 어떤 수와 0의 GCD는 자기 자신이다. gcd(n,0) = n

81과 27의 최대공약수를 구해보면
gcd(81,27) = gcd(27, 81%27) = gcd(27,0) = 27
몇 번만에 계산할 수 있다. 그러나 이 때에도 재귀 호출을 사용한다.

피보나치 수열