최대공약수(GCD)란?
GCD(Greatest Common Divisor, 최대공약수)는 0을 제외한 두 개 이상의 정수를 모두 나누어 떨어지게 하는 가장 큰 정수를 말합니다.
예를 들어 48과 180의 최대공약수를 소인수분해를 이용해 구해 보겠습니다.
48 = 2 × 2 × 2 × 2 × 3
180 = 2 × 2 × 3 × 3 × 5
두 수가 공통으로 가진 소인수는 2, 2, 3이므로 최대공약수는 2 × 2 × 3 = 12입니다.
문제 이해하기
정수 N과 K가 주어졌을 때, 같은 줄에 있는 임의의 두 숫자를 골라도 그 최대공약수가 항상 K가 되도록 N줄의 숫자를 출력하는 것이 이 문제의 목표입니다.
예를 들어 N=2, GCD=2가 입력으로 주어지면 다음과 같이 출력할 수 있습니다.
입력 : N=2, GCD=2 출력 : 2-4-6-10 14-16-18-22
첫 번째 줄의 2, 4, 6, 10 중 어떤 두 수를 골라도 최대공약수는 2이며, 두 번째 줄의 14, 16, 18, 22 역시 마찬가지입니다.
핵심 원리
이 문제의 핵심은 네 수 6i+1, 6i+2, 6i+3, 6i+5가 서로소라는 점입니다. 즉, 이 네 수 중 어떤 두 개를 골라도 최대공약수는 항상 1입니다.
- 연속한 두 수(6i+1과 6i+2, 6i+2와 6i+3)는 항상 서로소입니다.
- 차이가 2인 홀수 쌍(6i+1과 6i+3, 6i+3과 6i+5)은 공약수 후보가 1과 2뿐이지만 둘 다 홀수이므로 서로소입니다.
- 6i+1과 6i+5는 차이가 4이고 둘 다 홀수이므로 서로소입니다.
- 6i+2와 6i+5는 차이가 3이지만 둘 다 3의 배수가 아니므로 서로소입니다.
따라서 이 네 수에 K를 곱한 값들을 한 줄에 출력하면, 해당 줄의 모든 쌍이 정확히 K를 최대공약수로 갖게 됩니다.
알고리즘
시작
1단계 → 정수 n(예: 2), k(예: 2)와 반복 변수 i를 준비한다.
2단계 → i를 0부터 n-1까지 1씩 증가시키며 반복한다.
k × (6×i + 1)을 출력한다.
k × (6×i + 2)를 출력한다.
k × (6×i + 3)을 출력한다.
k × (6×i + 5)를 출력한다.
줄바꿈 문자를 출력한다.
3단계 → 반복이 끝나면 종료한다.
끝
C 언어 구현 예제
#include<stdio.h>
int main() {
int i, n = 2, k = 2;
for (i = 0; i < n; i++) {
printf("%d-", (k * (6 * i + 1)));
printf("%d-", (k * (6 * i + 2)));
printf("%d-", (k * (6 * i + 3)));
printf("%d", (k * (6 * i + 5)));
printf("\n");
}
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
2-4-6-10 14-16-18-22