유클리드 호제법

유클리드 호제법이란 두 수의 최대 공약수를 구할 때 쓰는 오래된 알고리즘이다.

a와 b의 최대공약수는 a%b와 b의 최대공약수와 같다는 방식이다. 그러다가 둘 중 한 수가 0이 되면 0이 아닌수가 최대공약수가 된다. 

최소공배수는 두 수의 곱에서 최대공약수를 나누면 된다.

 

---

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algorithm/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95.cpp

불러오는 중입니다...

C++ 코드

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}
int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}
int main()
{
	int n, m;
	cin >> n >> m;
	cout << "gcd is : " << gcd(n, m) << endl;
	cout << "lcm is : " << lcm(n, m) << endl;
	return 0;
}