유클리드 호제법(최대 공약수 구하기)

### 최대 공약수(GCD, Greatest Common Divider) ###

: 0이 아닌 두 정수나 다항식의 공통되는 약수 중에서 가장 큰 수

 

 

 

### 유클리드 호제법(Euclidean Algorithm) ###

: a % b = R이라고 했을 때,

 a와 b의 최대공약수는 b와 R의 최대공약수와 같다

=> GCD(a, b) = GCD(b, a%b) = GCD(b, a mod b)​

 

 

1.

#유클리드 호제법 사용
def GCD(a,b):
	if a % b == 0:
		return b 
	return GCD(b, a%b)


# 유클리드 호제법 반복문으로 변경 
def GCD(a,b):
	while a % b != 0:
		a, b = b, a%b 
	return b 

 

2. 라이브러리(math) 사용

import math 

math.GCD(a,b)

 

 

 

 

번외 크드는 그냥 최대 공약수를 구하는 것으로 속도가 느릴 수 있습니다.

그래서 위의 방법을 사용합니다.

​

​

 

번외 코드

def gcd(x,y):
    for i in range(min(x,y),0,-1):
        if x % i == 0 and y % i == 0:
            return i