[1658] 최대공약수와 최소공배수

문제

두개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

입력 파일의 첫째 줄에는 두 개의 자연수가 주어진다.

이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

---

예제 입력 

24 18

 

예제 출력

6
72

---

최대공약수(GCD) : 공약수는 최대공약수의 약수이다.

- 공약수 : 어떤 두 수 이상의 공통인 약수 

- 최대공약수 : 공약수들 중 가장 큰 수 

 

최대공약수를 구하기 위한 함수 

int gcd_get(int x, int y)
{
    int gcd;
    for (int i = 1; i <= x; i++)
    {
        if (x % i == 0 && y % i == 0)
        {
            gcd = i;
        }
    }
    return gcd;
}

gcd 를 구하고 1부터 특정 수까지 반복문을 돌리며 공통 약수를 확인한 후 gcd에 재 저장하는 방법으로, 연산이 마쳐진 후gcd는 최대공약수를 리턴한다.

- 지정된 수의 의 크기에 따라 시간이 초과될 위험이 있다는 것을 유념하여야 한다.

 

유클리드 호제법(Euclidean Algorithm)

- A를 B로 나눈 나머지가 r이라면 A와 B의 최대공약수는 B와 r의 최대공약수와 같다.

gcd(A, B) = gcd(B, r)

- 재귀적으로 A, B의 값을 줄여나가다가 B가 0이 되면 A가 최대공약수가 된다.

 

* while 문을 이용한 유클리드 호제법 

int gcd_get(int x, int y)
{
    int r;
    while (y != 0) // y 0이면 x가 최대공약수이므로 종료 
    {
        r = x % y; // 나머지를 구한 후
        x = y; // x를 y로
        y = r; // y를 r로 바꾸고 다시 반복한다.
    }
    return x; // 최대공약수를 리턴한다.
}

 

* 재귀함수를 이용한 유클리드 호제법 

int gcd_get(int x, int y)
{
    if (y == 0) return x; // y 0이면 x가 최대공약수이므로 종료 
    return gcd_get(y, x % y); // x와 y의 최대공약수는 y와 x%y의 최대공약수와 같다. 
}

 

- 어떤 두 수의 곱은 그 두수의 최대공약수와 최대공배수의 곱과 같다.  

- 두 수 a, b의 최대공약수를 gcd(a, b) 최소공배수를 1cm(a, b) 라하면 1cm(a, b) = a * b / gcd(a, b) 이 된다.

a * b = gcd(a, b) * 1cm (a, b)

 

 

- 위의 식에서 a * b가 커질경우 정수의 범위를 벗어나는 경우가 있으므로 쓰레기 값이 만들어질 우려가 있어 

- 크기가 벗어나서 터지는 우려 없이 다음과 같이 작성하는 것이 보다 안정적이다.

a / gcd(a, b) * b

 

최소공배수(LCM) : 공배수는 최소곱배수의 배수이다. (최소 공배수의 경우 따로 함수를 만들 필요는 없다)

- 공배수 : 어떤 두 수 이상의 공통인 배수 

- 최소공배수 : 공배수들 중 가장 작은 수 

---

입력형식

 

 

<입력의 설계>

코드를 구조화하여 gcd 와 lcm 을 구하는 함수를 각각 작성하였다. 

(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) 지시문에 따라 정수를 입력받을 변수 a, b와 위의 (1), (2)를 통해 얻은 gcd, lcm 값을 저장할 변수를 선언하였다. 

int a, b;
int gcd, lcm;

scanf("%d %d", &a, &b);

- 그리고 scanf 함수를 통해 지시문의 정수를 입력받았다. 

 

<출력의 설계>

함수를 통해 얻은 값을 각 변수에 저장하여준 후 출력하였다.

gcd = gcd_get(a, b);
lcm = lcm_get(a, b);

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

 

설계특징

GCD의 경우 유클리드 호제법을 사용하였고, LCM은 최대공배수를 구하는 방식을 사용하였다.  

 

제출답변

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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 a, b;
    int gcd, lcm;

    scanf("%d %d", &a, &b);

    gcd = gcd_get(a, b);
    lcm = lcm_get(a, b);

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

    return 0;
}