JUNGOL 실력키우기 1002 : 최대공약수, 최소공배수

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

첫째 줄에 N (2≤N≤10) 을 입력받고 다음 줄에 N개의 정수를 공백으로 구분하여 입력받는다.
입력받는 정수는 2이상 10 000 이하이다.데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.

 

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

[Copy] 3 2 8 10

[Copy] 2 40

---

 

저번 문제의 응용판입니다. 저번 함수 그대로 써도 될 듯 하네요

 

 

#include <iostream>
 
using namespace std;
 
int GetGCD(int a, int b);
int GetLCM(int a, int b);
 
int main(void)
{
    int n;    // 정수의 개수
    int *arr;        // 정수를 저장할 배열
    int maxFactor;        // 최대 공약수
    int minMultiple;    // 최소 공배수
 
    cin >> n;
 
    // 배열 동적 할당
    arr = new int[n];
 
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
 
    // 처음 두 수의 최대 공약수를 구한 뒤
    // 그 공약수와 다른 수의 최대 공약수를 구하는 것을 반복
    // 결과적으로 모든 수들의 최대 공약수를 얻을 수 있다.
    // 마찬가지 방법으로 최소 공배수도 얻어낸다.
    minMultiple = maxFactor = arr[0];
    for (int i = 1; i < n; ++i)
    {
        maxFactor = GetGCD(maxFactor, arr[i]);
        minMultiple = GetLCM(minMultiple, arr[i]);
    }
 
    cout << maxFactor << ' ' << minMultiple << endl;
 
    // 배열 해제
    delete[] arr;
}
 
// 최대 공약수 구하는 함수
int GetGCD(int a, int b)
{
    int r = a % b;
    if (r == 0)
        return b;
    GetGCD(b, r);
}
 
// 최소 공배수 구하는 함수
int GetLCM(int a, int b)
{
    // 공배수이므로 비교 숫자는 작은 수 의 배수로 증가해야할 것
    int num = (a < b) ? a : b;
 
    for (int i = num; ; i += num)
    {
        if (i%a == 0 && i%b == 0)
            return i;
    }
}

 

 

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