최대공약수 (Greatest Common Divisor - GCD)
두 수의 공약수 중 가장 큰 수를 뜻한다.
최소공배수 (Least Common Multiple - LCM)
두 수의 공배수 중 가장 작은 수를 의미한다.
lcm = 두 수의 곱 / gcd로 구할 수 있다.
유클리드 호제법
두 양의 정수의 최대공약수를 구하는 방법이다.
두 양의 정수 a, b(a > b)에 대하여 a = bq + r일 때 a와 b의 최대공약수는 b, r의 최대공약수와 같다.
r = 0이라면, a, b의 최대공약수는 b가 된다.
이를 파이썬으로 구현해보면 다음과 같다.
def Euclidean(a, b):
while b != 0:
r = a % b
a = b
b = r
return a
내부 과정을 확인해보면 아래와 같다.
def Euclidean(a, b):
while b:
print(f"a % b = r ~> {a} % {b} = {a % b}")
r = a % b
a = b
b = r
return a
Euclidean(15, 12)
# a % b = r ~> 15 % 12 = 3
# a % b = r ~> 12 % 3 = 0
# r == 0 일때 b가 3이므로 15와 12의 최대공약수는 3이다.
https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95
유클리드 호제법 - 나무위키
손으로 계산할 때는 제수와 피제수의 값 크기를 비교해서 적절하게 배열하지만 수식이나 코드로 나타낼 때는 신경쓰지 않아도 되는데, a일 때 a mod b ≡ a(a%b==a)이므로 Gcd(a,b)는 Gcd(b,a)를 호출한다
namu.wiki