유클리드 호제법

유클리드 호제법으로 최대공약수 구하기 (GCD)

// 기본 공식
 GCD(A, B) = GCD(B, A%B)
      if A%B = 0 -> GCD = B
          else GCD(B, A%B)    
    

최소공배수 (LCM)
최소공배수 = 두 자연수의 곱/ 최대공약수

백준2609번
최대공약수와 최소공배수를 유클리드 호제법을 사용하지 않고 풀었을때

#include <iostream>
using namespace std;

int main() 
{
	int n1, n2; 
	int Max = 1, Min = 1; // 최대 공약수, 최소 공배수
	cin >> n1 >> n2; // 두 개의 자연수 입력

	if (n1 == n2) 
    {
		cout << n1 << '\n'; // 최대공약수
		cout << n1 << '\n'; // 최소공배수
		return 0;
	}

	int k = (n1 < n2 ? n1 : n2); // n1<n2가 참이면 k=n1, 거짓이면 k=n2
	for (int i = 2; i <= k; i++) 
    {
		while (n1 % i == 0 && n2 % i == 0) // 같은 숫자로 여러번 나누어 떨어질 수 있음으로 while문 사용
        {
			Max = Max * i;
			n1 = n1 / i;
			n2 = n2 / i;
			i = 2; // i는 나눠지는 수를 찾기 위함이므로 찾았으면 다시 2부터 나눔
		}
	}
	Min = Max * n1 * n2;

	cout << Max << '\n'; // 최대공약수
	cout << Min << '\n'; // 최소공배수

	return 0;
}

백준1934번
최소공배수(유클리드 알고리즘 사용)

#include <iostream>
using namespace std;

int Gcd(int a, int b) // 최대공약수를 구하는 공식
{
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
		return Gcd(a, b);
	}
	else if (a == b)
		return Gcd(a, a % b);
	else if (b == 0)
		return a;
	else
		return Gcd(b, a % b);
}
int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << a * b / Gcd(a, b) << "\n"; // 두 자연수의 곱/최대공약수
	}

	return 0;

}