유클리드 호제법(Euclidean Algorithm)

유클리드 호제법(Euclidean Algorithm)은 두 정수 a, b 의 최대 공약수를 구하는 알고리즘이다.

 

두 정수 a, b의 최대 공약수는 a를 b로 나눈 나머지 r을 구한 후, b를 r로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되는 경우의 나머지를 최대 공약수로 간주한다.

 

과정을 수식으로 표현하면 a % b = r 이면 b % r = s를 계산하여 나머지가 0이 될 때 까지 반복한다.

 

예를 들어 a = 30, b 12일 경우 30 % 12 = 6, 12 % 6 = 0 이 되므로 6이 최대 공약수다.

 

JAVA로 표현하면 이렇게 표현할 수 있다.

int gcd(int a, int b){
	if(b==0) {
    	return a;
        }
    else{
    	return gcd(b,a%b);
        }
 }

 이를 이용해 최소 공배수 또한 구할 수 있다.

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