유클리드 호제법 (최대공약수)

유클리드 호제법 : 2개의 자연수 또는 정수의 최대공약수를 구하는 알고리즘이다.

---

서문

 

최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수

 

위 문제의 풀이 중 최대공약수를 링크와 같이 단순 무식하게 풀었는데

 

최대공약수를 구하는 알고리즘이 있어서 정리한다.

 

---

유클리드 호제법

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

---

원리

2개의 자연수 또는 정수를 직사각형의 한 변으로 가정하고 짧은 길이로 긴 길이를 나눈다.

 

그리고 나눈 나머지가 짧은 길이가 되고 원래의 짧은 길이가 긴 길이가 된다.

 

그리고 위 과정을 반복(재귀)해주다가 나누어 떨어져 0이 되는 순간의 짧은 길이가 최대공약수가 된다.

 

참조

 

프로그래머스 - 최대공약수와 최소공배수 [자바]

 

유클리드 호제법