#2702: 초6 수학

백준 2702번: 초6 수학

문제:

두 정수 a와 b 최소공배수는 두 수의 공통된 배수 중 가장 작은 수이고, 최대공약수는 두 수의 공통된 약수중 가장 큰 수이다.

a와 b가 주어졌을 때, 최소공배수와 최대공약수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 두 정수 a와 b로 이루어져 있고, 공백으로 구분되어 있다. (1 <= a,b <= 1,000)

풀이:

유클리드 호제법을 이용하여 최대공약수를 구한뒤 최대공약수와 최소공배수의 상관관계 공식을 이용하면 된다. 코딩 상에서는 a와 b의 나머지 값을 구한 뒤 a 위치에 b를 넣고 b에 위치에는 a%b를 넣는 재귀함수를 사용하면 된다.

코드:

#include <iostream>

using namespace std;

int gcd(int a, int b){
	if(b == 0){
		return a;
	}
	return gcd(b, a%b);
}

int main(void){
	int number;
	int numbers[2][1000];
	int answers[2][1000];
	int LCM;
	int GCD;
	cin >> number;
	
	for(int i = 0; i < number; i++){
		cin >> numbers[0][i];
		cin >> numbers[1][i];
	}
	for(int i = 0; i < number; i++){
		GCD = gcd(numbers[0][i], numbers[1][i]);
		LCM = numbers[0][i]*numbers[1][i]/GCD;
		answers[0][i] = LCM;
		answers[1][i] = GCD;
	}
	for(int i = 0; i < number; i++){
		cout << answers[0][i] << " ";
		cout << answers[1][i] << endl;
	}

}