[백준] 13241번: 최소공배수 [C++]

 

알고리즘 분류: 수학, 정수론, 유클리드 호제법

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

13241번: 최소공배수

 

 

【 풀이 】

 

유클리드 호제법을 재귀함수로 구현하여 최대공약수를 구한 다음

최대공약수를 활용하여 최소공배수를 구하면 되는 문제이다.

문제에서 수 형식을 long long int (C/C++) 를 사용하라고 하였으니, 변수든 함수든 모두 long long int로 구성하면 된다.

 

유클리드 호제법은 두 수의 나머지가 0이 될때까지 나누어서 최대공약수를 구하는 알고리즘이다.

예를 들어, 1071과 1029의 최대공약수를 구한다고 가정해보자.

• 1071은 1029로 나누어 떨어지지 않으므로 나머지를 구한다. => 42
• 1029는 42로 나누어 떨어지지 않으므로 나머지를 구한다. => 21
• 42는 21로 나누어 떨어진다. 즉 21은 1071과 1029의 최대공약수이다.

 

 

【 코드 】

 

#include<iostream>
using namespace std;

long long int ucl(long long int a, long long int b)
{
	long long int c;
	c = a % b;
	if (c != 0)
		return ucl(b, c);
	else
		return b;
}
int main(void)
{
	long long int c;
	long long int a, b;
	long long int result;
	cin >> a >> b;
	if (a > b)
		c = ucl(a, b);
	else
		c = ucl(b, a);
	result = c * (a / c) * (b / c);
	cout << result;
	return 0;
}