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

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

문제

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

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

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

코드

#include <iostream>

using namespace std;

/* 조건 */
#define MAX_VALUE 10001

/* 변수 */
int lhs, rhs;
int dividend, divisor, remainder;
int GCF, LCM; // Great Common Facotr, Least Common Multiple

/* 함수 */
void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    /* 입력 */
    cin >> lhs >> rhs;

    /* 풀이 */
    if(lhs < rhs) swap(&lhs, &rhs);

    dividend = lhs;
    divisor = rhs;

    while(remainder = dividend % divisor) {
        dividend = divisor;
        divisor = remainder;
    }
    GCF = divisor;

    LCM = lhs * rhs / GCF;

    /* 출력 */
    cout << GCF << '\n' << LCM << '\n';
}

풀이

유클리드 호제법

위키피디아 참고

두 수 a, b에 대해 (단, a > b)
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고,
다시 r을 r'로 나눈 나머지를 구하는 과정을 반복
나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

요약

제수, 피제수, 나머지를 이용해 최대공약수를 구하는 알고리즘

예시

1071과 1029의 최대공약수

이 때, 나누는 수인 21 이 두 수의 최대공약수이다.

코드로 구현

 while(remainder = dividend % divisor) {
    dividend = divisor;
    divisor = remainder;
}
GCF = divisor;
LCM = lhs * rhs / GCF;

나머지가 0일 때 반복문이 끝나며,
그 때의 나누는 수인 divisor 가 최대공약수(GCF)가 되며,
최소공배수(LCM)는 두 수를 곱하고 최대공약수로 나눈 값이 된다.

출처

백준 [02609] 최대공약수와 최소공배수
https://www.acmicpc.net/problem/2609