두 수의 k번째 공약수 출력하기 – 알고리즘과 C 코드 예제

두 개의 정수 x와 y가 주어졌을 때, 두 수의 k번째 공약수(kth common factor)를 찾아 출력하는 문제를 살펴보겠습니다. 이 문제는 반복문과 조건문만으로 해결할 수 있는 대표적인 기초 알고리즘 문제입니다.

문제 이해하기

예를 들어 x = 12, y = 18이라고 가정해 봅시다. 각 수의 약수는 다음과 같습니다.

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

따라서 두 수의 공약수는 1, 2, 3, 6입니다. 만약 k = 3이라면, 세 번째 공약수인 3을 출력해야 합니다.

입력 : x = 12, y = 18, k = 3
출력 : 3번째 공약수 = 3

알고리즘

두 수 x와 y, 그리고 몇 번째 공약수를 찾을지 결정하는 k 값을 입력받습니다.
반복문에서 사용할 변수 i와 num을 선언하고, 공약수의 개수를 세기 위한 count를 0으로 초기화합니다.
x < y이면 num에 x를 저장하고, 그렇지 않으면 num에 y를 저장합니다. 공약수는 두 수 중 작은 값보다 클 수 없으므로, 작은 값까지만 검사하면 됩니다.
i = 1부터 num까지 반복하면서 다음을 수행합니다.
- x % i == 0 이고 y % i == 0 이면, 즉 i가 두 수 모두를 나누어 떨어뜨리면 count를 1 증가시킵니다.
- count == k가 되는 순간 해당 i가 바로 k번째 공약수이므로 이를 출력하고 종료합니다.
반복이 끝날 때까지 k번째 공약수를 찾지 못했다면 공약수의 개수가 k개보다 적다는 뜻이므로 -1을 반환합니다.

C 언어 구현 예제

#include <stdio.h>

int main() {
    int x = 12, y = 18, k = 3; // 두 수 x, y와 찾고자 하는 공약수의 순서 k
    int i, num, count = 0;

    // 두 수 중 작은 값을 num에 저장
    if (x < y)
        num = x;
    else
        num = y;

    // 1부터 작은 수까지 반복하며 공약수 검사
    for (i = 1; i <= num; i++) {
        if (x % i == 0 && y % i == 0) { // 나머지가 0이면 공약수
            count++;
            if (count == k) {           // k번째 공약수를 찾은 경우
                printf("%d번째 공약수는 %d입니다.\n", k, i);
                return 0;
            }
        }
    }

    // 공약수의 개수가 k개보다 적은 경우
    printf("공약수의 개수가 %d개보다 적습니다.\n", k);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

3번째 공약수는 3입니다.

동작 원리 정리

이 알고리즘의 핵심은 1부터 두 수 중 작은 값까지 차례대로 검사하면서, 어떤 수 i가 x와 y를 모두 나누어 떨어뜨릴 때마다 카운트를 증가시키는 것입니다. 공약수는 항상 오름차순으로 발견되기 때문에, 카운트가 k에 도달한 시점의 i가 곧 k번째 공약수가 됩니다.

시간 복잡도는 두 수 중 작은 값에 비례하여 O(min(x, y))이며, 별도의 추가 메모리 없이 상수 공간으로 해결할 수 있어 효율적입니다. 참고로 최대공약수(GCD)를 먼저 구한 뒤 그 약수를 나열하는 방법을 사용하면 더 적은 연산으로 공약수 목록을 얻을 수도 있습니다.