GCD 계산 알고리즘

강현구·2022년 3월 31일
0

GCD = 최대공약수(Greatest Common Divisor)
초등학교 때, 많이 배웠던 두 수의 최대공약수 구하기.
코드를 통해서도 손쉽게 구할 수 있다.

  • GCD를 구하는 방법1
    gcd(12,8) -> max(1,2,4) -> 4
    도식적으로 8과 12를 각각 (4+4), (4+4+4)로 나타내고 둘 중 큰 수에서 작은 수를 뺀다.
    12 ==== ==== ====
    8 ==== ====
    -> 그렇게 나온 결과값에서 둘 중 큰 수에서 작은 수를 뺀다. (반복)
    8 ==== ====
    4 ====
    -> 반복
    4 ====
    4 ====
    -> 최종적으로 4와 0이 남게 되는데 여기서 남은 4가 두 숫자의 gcd가 된다.
    4 ====
    0
    이를 코드로 구현하면 다음과 같이 만들 수 있다.
gcd_sub(a,b):
	a, b = max(a,b), min(a,b)
	while a!=0 and b!=0:
    	a, b = b, a-b
    return a

이는 결국 두 수에서 나머지를 구하는 방법으로 동일하게 표현될 수 있다.

gcd_mod(a,b):
	a, b = max(a,b), min(a,b)
	while a!=0 and b!=0:
    	a, b = b, a%b
    return a
profile
한걸음씩

0개의 댓글