[C언어] 5618번

Q. 자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

 

입력.

첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다.

 

출력.

입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

 

---

 

처음에는 해결법을 다음과 같이 생각했다.

1. 입력받은 숫자를 소수로 나누고 그 횟수의 최솟값을 구한다.

2. 나누었던 소수와 그 횟수를 통해 나올 수 있는 수들을 오름차순으로 출력한다.

그런데 여기서는 두 번째 방식을 구현하는데 반복문을 사용하기 까다로워 어려움을 겪었다.

 

그러나 아래의 방식을 사용하면 간단히 문제를 해결할 수 있다.

 

" 1 ~ 입력받은 숫자 중 가장 작은 수를 나누어 공통적으로 나머지가 0인 숫자를 출력 "

 

 

#include <stdio.h>

int main(void) {
	int i, min, n;
	int arr[3] = {0, 0, 0};

	scanf("%d", &n);

	scanf("%d", &arr[0]);
	min = arr[0];

	if (n == 2) 
		scanf("%d", &arr[1]);
	else
		scanf("%d %d", &arr[1], &arr[2]);

	for (i = 1; i < n; i++)
		if (arr[i] < min)
			min = arr[i];

	for (i = 1; i <= min; i++)
		if (arr[0] % i == 0 && arr[1] % i == 0 && arr[2] % i == 0)
			printf("%d\n", i);
	
	return 0;
}