•
최대 공약수는 유클리드 호제법을 통해 구할 수 있다.
•
최대 공약수를 구하고자 하는 두 값 x,y 가 있고 x를 y로 나눈 나머지인 r이 있다고 하자.
•
x, y의 최대공약수는 y와 r의 최대 공약수와 같다.
•
x에 y값을 대입하고 y에는 r을 대입하는 것을 반복하다가 r이 0이 나오면 그때의 y값이 최대 공약수이다.
•
이를 함수로 작성하면
def gcd(x,y):
while y: # y > 0 일 때까지 반복
x, y = y, x%y
return x # y값은 x값에 대입된 상태
Python
복사
•
최소 공배수는 두 값을 곱한 것을 최대 공약수로 나눈 몫이다.
def lcm(x,y):
result = (x*y) // gcd(x,y)
return result
Python
복사