[1002] 6. 최대공약수, 최소공배수

문제

n개의 정수를 입력받아서 최대공약수와 최소공배수를 구하는 프로그램을 작성하여 보자.

입력

첫째 줄에 N (2≤N≤10) 을 입력 받고 다음 줄에 N개의 정수를 공백으로 구분하여 입력 받는다.

입력 받는 정수는 2이상 10,000 이하이다. 데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.

출력

입력받은 정수들의 최대공약수와 최소공배수를 공백으로 구분하여 출력한다.

최소공배수는 20억 이하의 정수이다.

---

예제 입력 

3

2 8 10

 

예제 출력

2 40

---

[1658]문제를 조금 확장한 형태인데, 여러개의 최대공약수와 최소공배수를 요구하고 있다.

가장 효율적인 방법(가장 많은 수의 최대공약수를 빠른 시간에 구하는 방법) 은 (1) a, b의 최대공약수를 구하고 (2) c의 최대 공약수를 구하는 것이다.

 

< 여러 수의 최대공약수(GCD), 최소공배수(LCM) 를 구하는 방법 >

- 세개의 수 a, b, c의 최대공약수를 구하기 위해서는 두수 a와 b의 최대공약수를 구한 결과와 c의 최대공약수를 구하면 된다. 

- gcd(a, b, c) = gcd (gcd (a, b), c)

- N개 수의 최대공약수는 N-1개 까지의 최대공약수를 구한 결과와 N번쨰 수의 최대공약수를 구하면 된다.

- 최소공배수 역시 앞의 수들의 최소공배수를 구한 결과와 현재수의 최소공배수를 구하면 된다.

gcd = a[0];
1cm = a[0];

for (int i = 1; i < n; i++)
{
	gcd = gcd_get(gcd, arr[i]);
	lcm = (lcm * arr[i]) / gcd_get(lcm, arr[i]);
}

 

<입력의 설계>

(1) gcd를 구하는 함수 

int gcd_get(int x, int y)
{
    while (y != 0)
    {
        int temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

(2) lcm을 구하는 함수 

int lcm_get(int x, int y)
{
    return (x * y) / gcd_get(x, y);
}

(3) 컴파일을 위해 gcd, lcm 의 함수 프로토타입 선언 (함수 정의가 뒤에 나올 거니까 에러 없이 넘기기)

int gcd_get(int a, int b);
int lcm_get(int a, int b);

(4) 이제 메인문의 입력 처리를 정리한다. 

다음과 같은 요소들을 선언한다. 

- 지시문에 따라 입력받을 n

- n의 값을 저장하고 gcd, lcm 의 값을 계산하기위해 사용될 arr 배열

- 최소공배수, 최대공배수의 값을 저장한 gcd, lcm

 

그리고 scanf 함수를 통해 n을 입력받는다

int n;
int arr[10];
int gcd;
int lcm;

scanf("%d", &n);

 

<출력의 설계>

앞서 다루었듯이, 효율적인 처리를 위해 a, b의 최대공약수를 구한 결과와 c의 최대공약수를 구하는 방식을 사용하였다. 

    for (int i = 1; i < n; i++)
    {
        gcd = gcd_get(gcd, arr[i]);
        lcm = (lcm * arr[i]) / gcd_get(lcm, arr[i]);
    }

 

제출답변

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int gcd_get(int a, int b);
int lcm_get(int a, int b);

int gcd_get(int x, int y)
{
    while (y != 0)
    {
        int temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

int lcm_get(int x, int y)
{
    return (x * y) / gcd_get(x, y);
}

int main()
{
    int n;
    int arr[10];
    int gcd;
    int lcm;

    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    gcd = arr[0];
    lcm = arr[0];

    for (int i = 1; i < n; i++)
    {
        gcd = gcd_get(gcd, arr[i]);
        lcm = (lcm * arr[i]) / gcd_get(lcm, arr[i]);
    }

    printf("%d %d", gcd, lcm);

    return 0;
}