[백준 C++] 2609 최대공약수와 최대공배수

문제

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

입력

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

출력

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

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

풀이

두수 a, b를 받을때, a < b로 수를 정렬한뒤에,
2부터 b보다 작거나 같은 수로 a, b가 동시에 나눠지면 이는 공약수이고,
이 가능한 약수들의 최대값이 최대공약수인것이다.
여기서, 최대공배수는 최대공약수에, 마지막으로 나누다남은 a , b의값들을 모저리 곱한것이므로

코드를 짤때 logc()함수로 최대공약수를 구하게하고,
이를 최대공약수를 리턴하는 GCD함수 와 최대공배수를 리턴하는 LCM함수에서 같이 사용했다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>

int logic(int a, int b) {
	if (a > b) { //a< b
		int temp = a;
		a = b;
		b = temp;
	}
	int res = 1;
	bool check = false;
	while (1) {
		for (int i = 2; i <= b; i++) {
			if (a % i == 0 &&
				b % i == 0) {
				check = true; //연산체크
				a /= i; //a, b를 모두 나누어서 다시저장
				b /= i;
				res *= i; //약수기록
			}
		}
		if (check) {
			check = false;
		}
		else {
			break;
		}
	}
	return res;
}

int LCM(int a, int b) {
	int res = logic(a, b); //최대공약수 여기에 a, b를 나눈몫을 각각곱해줘야함
	int a_q = a / res; //a, b를 최대공약수로 나누어 남은 몫만큼
	int b_q = b / res; //최대공약수들에 곱해주면 최대공배수가된다.
	res *= a_q * b_q;
	
	return res;
}

int GCD(int a, int b) {
	int res = logic(a, b); //최대공약수

	return res;
}

int main(void) {
	int a, b;
	scanf("%d%d", &a, &b); 

	printf("%d\n%d", GCD(a, b), LCM(a, b));
	return 0;
}