유클리드 호제법이란
유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
예시
1071과 1029의 최대공약수를 구하면,
1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42
1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 21
42는 21로 나누어떨어진다.따라서, 최대공약수는 21이다.
78696과 19332의 최대공약수를 구하면,
78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 + 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2따라서, 최대공약수는 36이다.
최소공배수
최소공배수는 최대공약수와 밀접한 관계가 있는데,
정수 a, b의 최대공약수 G = gcd(a, b)에 대하여 아래의 식을 만족하는 정수 x와 y가 존재한다.a = Gx, b = Gy (단, x, y는 정수)
이 때 a b = GGxy 임을 알 수 있고, G는 두 수의 최대 공약수이며 x와 y는 서로소인 관계를 가진다.
집합적으로 생각하면, a와 b의 합집합은 G, x, y이고 이 세 수를 곱한 Gxy가 최소공배수가 됨을 알 수 있다.
a b = GGxy
a b / G = GGxy / G (양변에 최소 공약수를 나누어 줌)
a * b / G = Gxy(최소공배수)최소공배수 = a * b / G
그러므로 두 수의 최소공배수 lcm(a, b)= a * b / gcd(a, b)
이를 활용해서 풀이한 알고리즘 문제
https://velog.io/@choiyunh/프로그래머스-Level1-최대공약수와-최소공배수
