[BOJ-2609][C++] 최대공약수와 최소공배수

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

24 18

 

예제 출력 1 

6
72

 

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 1번
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 고등부 1번

 

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

 

문제 출처

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

---

 

문제 해결 방법

• for 문을 이용하여 직접 계산하는 방법으로 문제를 해결하였다.
  • 최대 공약수(GCD)
    • for 문을 이용하여 변수 i가 1부터 입력 받은 두 수(n1, n2) 중 최댓값(maxN)까지 순회를 하면서 두 수(n1, n2)와 모두 나누어 떨어질 경우, 그 때의 변수 i를 변수 gcd에 넣는다.
    • for 문이 종료될 때, gcd 변수에는 두 수(n1, n2)로 나누어 떨어지는 i의 최댓값가 할당되게 된다.
  • 최소 공배수(LCM)
    • for 문을 이용하여 변수 i가 1부터 입력 받은 두 수(n1, n2)를 곱한 값(n1 * n2)까지 순회를 하면서 두 수(n1, n2)에 의해 나누어 떨어질 경우, 그 때의 변수 i를 변수 lcm에 넣는다.
    • 그리고 for 문을 종료시켜준다.
    • for 문이 종료될 때, lcm 변수에는 두 수(n1, n2)에 의해 나누어 떨어지는 i의 최솟값이 할당되게 된다.
  • 최종적으로 gcd 변수에는 두 수의 최대 공약수가, lcm 변수에는 두 수의 최소 공배수가 넣어지게 된다.

pair<int, int> findAnswer(int n1, int n2) {
    int maxN, gcd, lcm;
    pair<int, int> ans;

    maxN = max(n1, n2);    // 최댓값 찾기
    
    // 최대 공약수(GCD) 찾기
    for (int i = 1; i <= maxN; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }

    // 최소 공배수(LCM) 찾기
    for (int i = 1; i <= n1 * n2; i++) {
        if (i % n1 == 0 && i % n2 == 0) {
            lcm = i;
            break;
        }
    }

    ans = make_pair(gcd, lcm);
    return ans;
}

 

• 또는 다음과 같이 재귀 함수를 이용하여 문제를 해결해도 된다. (유클리드 호제법)

// GCD : 최대공약수
int gcd(int n1, int n2) {
	if (n1 == 0) return n2;
	else return gcd(n2 % n1, n1);
}

// LCM : 최소공배수
int lcm(int n1, int n2) {
	return (n1 * n2) / gcd(n1, n2);
}

 

코드

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

int num1, num2;

pair<int, int> findAnswer(int n1, int n2) {
    int maxN, gcd, lcm;
    pair<int, int> ans;

    maxN = max(n1, n2);    // 최댓값 찾기
    
    // 최대 공약수(GCD) 찾기
    for (int i = 1; i <= maxN; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }

    // 최소 공배수(LCM) 찾기
    for (int i = 1; i <= n1 * n2; i++) {
        if (i % n1 == 0 && i % n2 == 0) {
            lcm = i;
            break;
        }
    }

    ans = make_pair(gcd, lcm);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> num1 >> num2;

    cout << findAnswer(num1, num2).first << '\n' << findAnswer(num1, num2).second << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정수론 및 조합론]
• 브론즈I