알고리즘(C++) / 백준 2609 : 최대공약수와 최소공배수

2609

www.acmicpc.net/problem/2609

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

 

문제

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

 

입력

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

 

출력

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

 

코드

//2609 최대공약수와 최소공배수
#include <iostream>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;

	int small = 0;
	int min, max;

	if (a < b)
		small = a;
	else
		small = b;

	for (int i = small; i > 0; i--) {
		if (a % i == 0 && b % i == 0) {
			max = i;
			cout << max << endl;
			break;
		}
	}//최대공약수

	min = max * (a / max) * (b / max);
	cout << min << endl;
	//최소공배수

	return 0;
}

 

결과

 

설명

이번 문제는 최대공약수와 최소공배수를 구하는 문제이다. max에 최대 공약수를 min에 최소 공약수 값을 저장한다. 

두 수를 나눠 나머지가 0인 수 중 가장 큰 수가 최대 공약수이다. 입력받은 두개의 수 중 작은 수부터 1까지 반복하여 최대 공약수를 찾아낸다. 최소 공배수는 최대 공약수 * (a/최대공약수) * (b/최대공약수)로 구할 수 있다.