두 수의 공약수를 구하는 C++ 프로그램

두 수의 공약수란?

두 숫자의 공약수(common divisor)란 두 수 모두를 나머지 없이 나눌 수 있는 수를 의미합니다.

예를 들어,

• 12의 약수: 1, 2, 3, 4, 6, 12
• 18의 약수: 1, 2, 3, 6, 9, 18

따라서 12와 18의 공약수는 1, 2, 3, 6입니다.

최대공약수(GCD)의 개념

이들 공약수 중 가장 큰 수를 두 수의 최대공약수(Greatest Common Divisor, GCD)라고 부릅니다. 일반적으로 두 정수 a와 b의 최대공약수는 (a, b)로 표기하며, 따라서 (12, 18) = 6이 됩니다.

최대공약수가 중요한 이유

최대공약수는 다양한 분야에서 활용됩니다. 대표적인 예로 두 수의 최소공배수(LCM), 즉 두 수의 공통 배수 중 가장 작은 양의 정수를 계산할 때 사용됩니다.

두 수 a와 b의 최소공배수는 다음 공식으로 구할 수 있습니다.

LCM(a, b) = (a × b) ÷ GCD(a, b)

예를 들어, 12와 18의 최소공배수는 다음과 같습니다.

LCM(12, 18) = (12 × 18) ÷ 6 = 36

문제 정의

입력: a = 10, b = 20
출력: 1 2 5 10
// 10과 20의 모든 공약수는 1, 2, 5, 10

알고리즘 설명

구하고자 하는 값은 두 수를 나머지 없이 정확히 나눌 수 있는(나누어 떨어지는) 정수들입니다. 1부터 두 수 중 작은 값까지 차례대로 확인하면서, 각 숫자 i가 n1과 n2 모두를 나누어 떨어지게 하는지 검사하면 됩니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int main() {
    int n1, n2, i;
    n1 = 10;
    n2 = 20;

    for(i = 1; i <= n1 && i <= n2; ++i) {
        if(n1 % i == 0 && n2 % i == 0) {
            cout << i << "\t";
        }
    }
    return 0;
}

코드 동작 원리

1. 변수 n1과 n2에 각각 10과 20을 저장합니다.
2. 반복문이 1부터 두 수 중 작은 값(n1 = 10)까지 실행됩니다.
3. 각 반복마다 조건식 n1 % i == 0 && n2 % i == 0을 통해 i가 두 수 모두를 나누어 떨어지게 하는지 확인합니다.
4. 조건을 만족하는 i만 탭 문자와 함께 출력합니다.

프로그램을 실행하면 10과 20의 공약수인 1, 2, 5, 10이 순서대로 출력됩니다. 이 방법은 시간 복잡도가 O(min(a, b))로 단순하지만, 유클리드 호제법을 사용하면 최대공약수를 훨씬 빠르게 구할 수도 있습니다.