유클리드 호제법 최대공약수 최소공배수 구하기

유클리드 호제법이란?

 

유클리드 互除法 / Euclidean algorithm

互(서로 호), 除(나눌 제, 뺄 제) 서로 나눈다는 의미입니다.

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 알고리즘입니다. 인류 최초의 알고리즘이라고 하네요.

 

 

출처 나무위키

 

출처 나무위키

gcd는 최대공약수를 뜻합니다.

Greatest Common Divisor의 줄임말입니다.

 

 

자바 코드로 나타내면

// 반복문 방식
int gcd(int a, int b) {
	
	while(b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}
 
// 재귀 방식
int gcd(int a, int b) {
	if(a%b == 0) return b;
	return gcd(b, a % b);
}

이렇게 됩니다.

 

최소공배수는

a * b / 최대공약수입니다.