[Algorithm] 최대공약수 구하기 - 유클리드 호제법

유클리드 호제법

a와 b의 최대공약수는 (a를 b로 나눈 나머지)와 b의 최대공약수와 같다.

큰 수를 작은 수로 나누어 구한 나머지로 큰 수를 대체한다.
큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다.
나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다.

Python 코드

a, b = 315, 495
if(b > a) : a, b = b, a

while(b!=0):
  a = a % b
  a, b = b, a

print(a)

a, b의 최대공약수는 (a - b),   b의 최대공약수와 같다.

큰 수에서 작은 수를 뺀다. 같아질 때까지 큰 수를 작은 수만큼 줄이는 것을 반복한다.
같아지면 그 수가 최대공약수이다.

Python 코드

a, b = 315, 495

wihle(a!=b):
	if(a > b) : a-=b
    else 	  : b-=a
    
print(a)