최대공약수와 최소공배수 알고리즘 c++

최대공약수 구하기

1. 큰 수를 작은 수로 mod 연산을 한다.
2. mod연산의 결과가 0이 나올 때까지 반복한다.
3. 이 때 나누는 수로 사용된 수가 두 수의 최대공약수가 된다.

코드로 구현하면

int gcd(int a, int b)
{
	int c = a % b;
	while (c > 0)
	{
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}

최소공배수 구하기

최대공약수 * 최소공배수 = 두 수의 곱
최소공배수 = 두 수의 곱 / 최대공약수

int lcm(int a, int b)
{
	return (a * b) / gcd(a, b);
}

---

BOJ 2609

백준 2609

전체 코드

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
	int c = a % b;
	while (c > 0)
	{
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}

int lcm(int a, int b)
{
	return (a * b) / gcd(a, b);
}

int main()
{
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << "\n" << lcm(a, b);
}