[Basic Algorithm] 최대공약수, 최소공배수 (by. 유클리드 호제법)

최대공약수 (Greatest Common Divisor)

• 두 수의 공통 약수 중 가장 큰 수
• Basic GCD Algorithm

for i in range(min(a,b),0,-1):
	if a%i==0 and b%i==0:
    	print(i)
        break

최소공배수 (Least Common Multiple)

• 두 수의 공통 배수 중 가장 작은 수

for i in range(max(a,b),(a*b)+1):
	if i%a==0 and i%b==0:
    	print(i)
        break

유클리드 호제법

• x,y의 최대공약수는 y,r의 최대공약수와 같다는 원리 이용
• (이때, x%y=r)

def GCD(x,y):
	while x%y!=0:
    	x,y=y,x%y 
    return x

def LCM(a,b):
	result=(x*y)//GCD(x,y)
    return result