[python] 최대공약수 유클리드 호제법 알고리즘

최대공약수 

정수들의 공약수는 동시에 그들 모두의 약수인 정수이다. 공약수 가운데 가장 큰 것을 최대공약수라고 한다. 

 

유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 두개의 자연수 a, b (a > b)가 있다고 할 때 a, v에 대해서 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대 공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 떄 나누는 수가 a와 b의 최대공약수 이다. 

 

1. 반복되는 규칙 찾기 

• 두 정수 a, b의 최대 공약수 gcd( a, b ) 를 구하고자 하낟. 
• a를 b로 나눈 나머지를 r이라고 한다.
• a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 
• b와 r에 대하여 위의 방법을 반복적으로 적용한다. 
• 위 방법을 반복적으로 적용하여 나머지가 0이 되었을 때, 나누는 수가 a, b의 최대공약수이다. 

 

 

2. 해결방법 

유클리드 호제법은 같은 연산이 반복되고 종료조건으로 r이 0이 될때, 위에 식에서는 b가 0으로 들어올 때  종료조건을 만족 함으로 재귀적으로 해결할 수 있겠다. 

 

1. a, b를 나눈다.
2. 나머지 r을 저장한다. 
3. b와 r을 나눈다. 
4. 나머지 r'을 저장한다.
5. 위의 과정을 나머지가 0이 될때까지 반복한다.

 

3. 유클리드 호제법 재귀함수로 구현

# 유클리디안 
def Euclidean(a, b):	
	if (b==0):
		return a
	return Euclidean(b, a%b)


test_case = int(input())
for i in range(test_case):
    a,b = map(int, input().split(" "))

    print(Euclidean(a,b))