[CryptoHack] Greatest Common Divisor

GCD(Greatest Common Divisor): 최대공약수

-> 두 숫자 (a,b)의 가장 큰 약수

 

ex)

a = 8, b = 12 인 경우

a의 약수 = {1, 2, 4, 8}
b의 약수 = {1, 2, 3, 4, 6, 12}

따라서 gcd(a, b) = 4

 

 

if 만약, a 와 b 가 소수(prime number)인 경우 then gcd(a, b) 는 무조건 1 이다.

=> gcd(x, y) = 1 인 경우, x와 y는 서로소(coprime number) 이다.

 

---

Euclidean algorithm (유클리드 호제법, 유클리드 알고리즘)

두개의 자연수의 최대공약수를 구하는 알고리즘

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

(출처: 위키피디아)

 

ex)

출처: 위키피디아

 

 

 

이를 파이썬 알고리즘으로 만들어보자!

 

def gcd(a, b):
    while (b != 0):
        r = a % b
        a = b
        b = r
    return abs(a)

 

저는 요렇게 만들었는데요

 

b가 0이 아닌 경우 (즉, 나중에 나머지 r이 들어가므로 a와 b가 나누어 떨어지지 않은 경우까지 while 문이 돌아감)

나머지 r을 계산해주고 (mod 계산인 % 를 하면 나머지가 나옴)

a에는 나눠준 b 값을 넣고 (크던 작던 상관없음, 어차피  a = b로 순환하기 때문에)

b에는 나머지값을 넣어준다

이렇게 계속 나눠 떨어지기 직전까지 반복하다가 b=0이 되고 a=최대공약수가 될 때 절댓값(abs 함수)을 씌워서 a를 출력해준다! (음수가 나올 수도 있기 때문에)

 

퀴즈)

 

 

풀이)

 

이렇게 하면 답은

요로코롬 잘 나오네여