최대공약수는 2 숫자간의 공통된 약수 중 가장 큰 수를 말한다.
호제법이라는 말은, 두 수가 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.
최대공약수는
a와 b라는 수가 있을때
while b:
a, b = b, a % b
return a
이런식으로 구한다.
a = 3 , b = 12 일 경우 최대공약수는 '3' 이다.
a = 2 , b = 5 일 경우 최대공약수는 '1' 이다.
이걸 위의 유클리드 호제법을 사용해서 구하게 되면
이런식으로 쉽게 구할 수 있다.
최소공배수는 두 수의 배수 중 공배수에서 가장 작은 수를 구하면 됩니다.
만약
x = ab
y = bc 가 있으면
소인수분해를 했을때,
최대 공약수는 'b'가 됩니다.
최소 공배수는 abc가 됩니다.
그리고 여기서 x와 y를 곱하게 되면
xy = a b^2 c 가 되고
xy /b = abc가 되면서
최소공배수는 두 수를 곱한 값을 최대공약수로 나눈값이 됩니다.
위에 했었던 값들 중
3과 12의 최소 공배수는 12
2와 5의 최소공배수는 10이 됩니다.
이런식으로 최소공배수와 최대공약수를 쉽게 구할 수 있다.