JUNGOL 실력키우기 1658 : 최대공약수와 최소공배수

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

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

 

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

[Copy] 24 18

[Copy] 6 72

 

---

​요즘 보는 문제들은 힌트들이 상세히 적혀있어서 푸는데 크게 문제는 없는 듯 합니다. 다만 실제 실력 향상을 위해 제시된 모든 코드를 실제 구현해 보는 것이 좋을 것 같네요.

 

 

#include <iostream>
#include <cmath>
 
using namespace std;
 
int GetGDC(unsigned n1, unsigned n2);
int GetLCM(unsigned n1, unsigned n2);
 
int main(void)
{
    unsigned n1, n2;            // 자연수 두개
    unsigned maxFactor;    // 최대 공약수 저장용 변수
    unsigned minMultiple;// 최소 공배수 저장용 변수
 
    // 최대 공약수, 최소 공배수 초기화
    maxFactor = minMultiple = 1;
 
    // 두 개의 자연수를 입력 받는다.
    cin >> n1 >> n2;
 
    // 각 함수를 이용하여 최대공약수와 최소공배수를 찾는다.
    maxFactor = GetGDC(n1, n2);
    minMultiple = GetLCM(n1, n2);
 
    // 결과 출력
    cout << maxFactor << endl;
    cout << minMultiple << endl;
}
 
// 최대 공약수(GCD) 찾기
int GetGDC(unsigned n1, unsigned n2)
{
    // 반복문 사용
    //unsigned smallN = (n1 < n2) ? n1 : n2;
    //for (int i = 1; i <= smallN; ++i)
    //{
    //    // 두 수 모두 나눠지면 두 수의 공약수
    //    // i가 증가하므로 나중에 대입되는 값이 더 큰 공약수일 것
    //    maxFactor = (n1 % i == 0 && n2 % i == 0) ? i : maxFactor;
    //}
 
    // 유클리드 호제법 사용
    // r = n1 % n2 일때, n1과 n2와 최대 공약수는 n2와 r의 최대 공약수와 같다.
    //unsigned r;
    //while (true)
    //{
    //    r = n1 % n2;
 
    //    if (r == 0)
    //        break;
 
    //    n1 = n2;
    //    n2 = r;
    //}
    //return n2;
 
    // 유클리드 호제법 재귀 함수 사용
    unsigned r = n1 % n2;
    if (r == 0)
        return n2;
    return GetGDC(n2, r);
}
 
// 최소 공배수(LCM) 찾기
int GetLCM(unsigned n1, unsigned n2)
{
    unsigned bigN = (n1 > n2) ? n1 : n2;
    for (int i = bigN; ; ++i)
    {
        // 두 수의 공통된 배수가 되어야 하므로 최소한 큰 자연수와 같은 값이 올 것
        // i를 두 수로 나눴을 때 모두 나머지가 0 이면 공배수
        // 가장 먼저 등장한 것이 최소 공배수가 될 것
        if (i%n1 == 0 && i % n2 == 0)
        {
            return i;
        }
    }
}

 

 

JUNGOL) 문제은행) 실력키우기) 최대공약수와최소공배수