[수학] 유클리드 호제법

 

https://ko.wikipedia.org/wiki/유클리드_호제법

유클리도 호제법이란 최대공약수를 구하는 방법을 말한다. 

예시)))))

1071과 1029의 최대공약수 구하기 

1. 1071을 1029로 나누기 --->나머지 42

2.1029를 42로 나누기 --->나머지 21

3. 42를 21로 나누기 --->나머지0 

따라서 최대공약수는 21이다. 

 

자바 알고리즘으로 구현하기 

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

매우 쉬운 알고리즘이다. 

 

이상황에서 최소공배수를 구하려면 

최소공배수 = a*b/최대공약수 이다.

 

초등학교 때 배운 최소공배수 최대공약수이지만 [유클리드 호제법]이란 개념은 대학교 암호학 수업이후 처음 들어 포스팅 해보았다.