백준 13241 - 최소공배수

두 수가 주어졌을 때 최소공배수를 구하는 문제입니다.

최소공배수는 최대공약수를 이용해 구할 수 있습니다.
최대공약수는 유클리드 호제법 이라는 알고리즘을 이용해 빠르게 구할 수 있습니다.

#include<iostream>

long long int gcd(const long long int a, const long long int b);

int main()
{
	std::cin.tie(NULL);
	std::ios_base::sync_with_stdio(false);

	long long int a, b, result = 1;
	std::cin >> a >> b;

	long long int temp = gcd(a, b);

	result = a * b / temp;

	std::cout << result << "\n";

	return 0;
}

long long int gcd(const long long int a, const long long int b)
{
	long long int copy_a;
	long long int copy_b;
	if (a < b)
	{
		copy_a = b;
		copy_b = a;
	}
	else
	{
		copy_a = a;
		copy_b = b;
	}

	long long int r;
	while (copy_b != 0)
	{
		r = copy_a % copy_b;
		copy_a = copy_b;
		copy_b = r;
	}

	return copy_a;
}