c++ 문제 풀이 - 최대 공약수, 최소 공배수

학교에서 선생님께서 주신 문제가 있습니다.

최대 공약수 구하기 및 최소 공배수 구하기입니다.

 

최대 공약수

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int a, b;
	int c;

	cin >> a >> b;

	while (b != 0)
	{
		c = a % b;
		a = b;
		b = c;
	}
	cout << a << endl;
	
}

 

 

두 정수 a와 b를 입력받습니다.

while 루프를 통해 b가 0이 될 때까지 a % b 연산을 반복하여 최대공약수를 구합니다.

b가 0이 되면, a에 최대공약수가 저장되어 출력됩니다.

 

 

이제 최소 공배수를 구해 볼까요

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int a, b;
	int c;
	int cnt;

	cin >> a >> b;

	cnt = a * b;

	while (b != 0)
	{
		c = a % b;
		a = b;
		b = c;
	}
	
	cout << cnt / a;

}

 

 

두 정수 a와 b를 입력받습니다.

cnt = a * b를 계산하여 두 수의 곱을 저장합니다.

유클리드 호제법을 사용하여 **최대공약수(GCD)**를 구합니다.

최소공배수(LCM)는 LCM(a, b) = (a * b) / GCD(a, b) 공식을 사용하여 계산됩니다.

결과를 출력합니다.