[정수론] 유클리드 호제법

📌 유클리드 호제법

⭐ 개념

• 두 수의 최대공약수(GCD)를 구하는 알고리즘
• MOD() 나머지 연산을 재귀적으로 활용

⭐ 실행과정

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행
2. 앞단계에서의 작은 수와 MOD 연산 결과값(나머지)로 MOD연산을 수행
3. 재귀적으로 진행하면서 나머지가 0이되는 순간 작은수가 최대공약수

✅ 최대공약수와 최소공배수의 관계

최소공배수 = A * B / 최대공약수

✅ a, b 누가 더 큰지 상관없는 이유

• 처음에 a가 b보다 작은 값이 들어오면 getGCD()함수를 지나면서 SWAP되는것과 같은 현상이 일어난다.

⭐ 코드

public static int getGCD(int a, int b) {
	if(b == 0) {
		return a;
	}
	return getGCD(b, a%b);
}