[BaekJoon/C++] 2609번 최대공약수와 최소공배수

2609 백준 - 최대공약수와 최소공배수

문제 링크: https://www.acmicpc.net/problem/2609

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

문제: 

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

 

접근 방법:

이 문제는 두 수의 최대공약수를 먼저 구한 다음 최대공약수를 활용하여 최소공배수를 풀면 끝나는 간단한 문제다. 최소공배수는 자연수 a와 b를 곱해준 값에 최대공약수를 나눠주면 된다. 두 수 a와 b 중 a가 b보다 더 작다고 가정해보자. 그렇다면 최대공약수는 a와 같거나 작을 수 밖에 없다. 그렇기 때문에 a를 기준으로 1씩 빼주면서 a와 b를 해당 수로 나눴을 때 나머지가 0일 경우를 찾는다. 그 중 가장 큰 수가 최대공약수이다. 최대공약수를 구한 뒤, 위에서 말한 연산을 통하여 최소공배수를 구할 수 있다.   

#include <iostream>


using namespace std;

int main() {
	int a, b;
	int max = 1;
	int min = 1;


	cin >> a >> b;

	if (a > b) {
		for (int i = b; i >= 1; i--) {
			if (a % i == 0 && b % i == 0) {
				max = i;
				break;
			}
		}
	}
	else {
		for (int i = a; i >= 1; i--) {
			if (a % i == 0 && b % i == 0) {
				max = i;
				break;
			}
		}
	}
	min = a * b / max;
	cout << max << '\n' << min << endl;
	return 0;
}