두 수의 공약수(common divisor)란 두 수를 모두 나누어 떨어지게 하는 수를 말합니다.
예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12이고, 18의 약수는 1, 2, 3, 6, 9, 18입니다. 따라서 12와 18의 공약수는 1, 2, 3, 6이며, 이 중 가장 큰 값인 6을 두 수의 최대공약수(GCD, Greatest Common Divisor)라고 부릅니다. 수학에서는 일반적으로 두 정수 a와 b의 최대공약수를 (a, b)로 표기하므로, (12, 18) = 6이라고 쓸 수 있습니다.
최대공약수는 여러 분야에서 중요하게 활용됩니다. 대표적인 예가 바로 두 수의 최소공배수(LCM), 즉 두 수의 공통 배수 중 가장 작은 양의 정수를 구하는 것입니다. 두 수 a와 b의 최소공배수는 다음 공식으로 계산할 수 있습니다.
a × b ÷ (a, b)
예를 들어, 12와 18의 최소공배수는 12 × 18 ÷ (12, 18) = 216 ÷ 6 = 36입니다.
문제
입력: 4, 10, 16, 14
출력: 2
설명
두 개 이상의 정수에 대한 최대공약수(GCD)란, 해당 숫자들을 나머지 없이 모두 나눌 수 있는 가장 큰 정수를 의미합니다.
예시 코드
#include <iostream>
using namespace std;
int gcd(int a, int b) {
int temp;
while(b > 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a[] = {4, 10, 16, 14};
int n = 4;
int r = a[0];
for(int i = 1; i < n; i++) {
r = gcd(r, a[i]);
}
cout << r << endl;
return 0;
}
출력 결과
2
코드 동작 원리
위 코드는 유클리드 호제법(Euclidean Algorithm)을 이용해 두 수의 최대공약수를 구합니다. 유클리드 호제법은 a를 b로 나눈 나머지를 반복적으로 계산하면서, 나머지가 0이 될 때의 나누는 수가 곧 최대공약수라는 원리를 기반으로 합니다.
배열처럼 세 개 이상의 숫자에 대해서도 확장이 가능합니다. 먼저 배열의 첫 번째 요소를 초기값으로 설정한 뒤, 나머지 요소들을 차례대로 순회하면서 현재까지의 GCD와 각 요소의 GCD를 반복해서 구하면 됩니다. 위 예시에서는 gcd(4, 10) = 2, gcd(2, 16) = 2, gcd(2, 14) = 2 순으로 계산되어 최종 결과인 2가 출력됩니다.