[백준 알고리즘] 2609번 : 최대공약수와 최소공배수 (C++) 문제 풀이

문제

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

입력

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

출력

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

 

출처

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

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

• 데이터를 추가한 사람: circlecho, jsh587

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

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

문제풀이

최대공약수와 최소공배수를 동시에 묻는 문제이며, 수학적 원리만 안다면 그렇게까지 어려운 문제는 아니다.

백준알고리즘 solved.ac 에 실버5에 랭크된 문제이다.

우선, 먼저 최대공약수를 구한 뒤,

주어진 2개의 수를 최대공약수로 나눈뒤

2개 결과값과 최대공약수를 곱하면 최소공배수가 나온다.

이는 코드에 다 나와있으니 참고하면 좋을 것 같다.

 

내 소스 코드 

#include<iostream>
using namespace std;
int main() {
    int num1, num2;
    cin >> num1 >> num2;
    int i = 1;
    int min;
    int min_result = 1;
    int max_result = 1;
 
    if (num1 > num2) {
        min = num2;
    }
    else min = num1;
 
    while (min >= i) {
        if (num1 % i == 0 && num2 % i == 0) {
            min_result = i;
        }
        i++;
    }
    max_result = min_result;
    max_result *= num1 / min_result;
    max_result *= num2 / min_result;
 
    cout << min_result << endl << max_result << endl;
 
    return 0;
 
 
 
}