[Algorithm][Python] 최대공약수(gcd)(유클리드 호제법)

최대공약수(Greatest Common Divisor)

두 수 x와 y가 주어졌을 때 두 수의 공통인 약수 중에서 가장 큰 약수를 최대공약수라고 한다. 최대공약수를 구하는 방법 중에서 하나인 유클리드 호제법을 사용해서 구할 것이다. 

 

유클리드 호제법(Euclidean algorithm)

1. x,y를 입력받는다.(x>y)

2. y가 0이면, m을 출력하고 종료한다.

3. x를 y로 나눈 나머지를 구한다.

4. 나머지를 y에 대입하고, 원래 y를 x에 대입한다.

5. 2번으로 돌아간다.

 

파이썬 코드

 

def gcd(x,y): 		# 1번
    while(True):	
        if(y==0): break # 2번
        x,y=y,x%y	# 3번,4번
    return x

print(gcd(30,16))

# 출력결과
# 2

 

파이썬 내장함수를 이용한 방법

 

from math import gcd

print(gcd(30,16))

# 출력결과
# 2