두 수의 최대 공약수를 구할때 여러 방법이 있다.
나는 두 수의 소인수 분해를 통해서 최대 공약수를 구했다.
최대 공약수 구한 방법
1. 각 수를 소인수 분해한다.
2. 소인수 분해한 것들 중 겹치는 찾는다.
3. 찾은 소인수를 다 곱한다.
그러나 그 과정을 구현하는데 오래걸렸다.
그래서 찾아본 결과 공약수를 구하는 알고리즘인 유클리드 호제법이란 것이 있었다.
유클리드 호제법이란?
두 수 a,b가 있을 때 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수가 된다. ( 단 a > b )
이 과정을 통해 a = bx + r로 만들고 b = rx' + r' / r = r'x'' + r'' 등으로 만든다.
이때 나머지가 0이되면 마지막으로 나눈 수가 a,b의 최대 공약수가 된다.
30 과 18를 호제법을 이용해 최대 공약수를 구하면
1. 30 = 18 * 1 + 12
2. 18 = 12 * 1 + 6
3. 12 = 6*2 + 0
따라서 30과 18의 최대 공약수는 6이 된다.
소인수 분해를 통해 최대 공약수를 구하면
30 = 2 x 3 x 5
18 = 2 x 3 x 3
겹치는 소인수는 2, 3이므로 최대 공약수는 6
108 과 42를 호제법으로 구하면
108 = 42 * 2 + 24
42 = 24 * 1 + 18
24 = 18 * 1 + 6
18 = 6 * 3 + 0
따라서 108과 42의 최대 공약수는 6이 된다.
최소 공배수 구하기
최소 공배수는 최대 공약수에 최대 공약수를 제외한 약수를 모두 한번씩만 곱한것이다.
예를 들어 30과 18의 약수는
30 = 2 x 3 x 5
18 = 2 x 3 x 3
최대 공약수 : 6
남은 약수 3, 5
따라서 최소 공배수는 6 x 3 x 5 = 90이 된다.
또 다른 방법으로는 두 수를 곱하고 최대 공약수를 나눠도 된다.
30, 18의 최대 공약수 6
30 x 18 = 540
최소 공배수 540 / 6 = 90