[JAVA]유클리드 호제법이란?

유클리드 호제법은 두 정수의 최대 공약수를 재귀적으로 구하는 방법입니다.

방식은 간단합니다.

100과 10의 최대 공약수를 구한다고 했을 때,

10,100%10이 다시 재귀로 함수 안에 들어갑니다.

그렇게 되면 100%10은 0이므로 첫번째 조건에 들어가고 10이 반환됩니다.

재귀 종료 조건은 큰 값을 작은 값으로 나누었을 때의 나머지가 0일 때이므로 첫 번째 조건은 n_2이==0이다.

그렇지 않으면 큰 값을 작은 값으로 나눈 나머지와 작은 값을 다시 함수에 넣지요.

 

static int gcd(int n_1, int n_2) {
	if(n_2==0) {
		return n_1;
	}
	else {
		return gcd(n_2,n_1%n_2);
				}
}
public static void main(String[] args) {
	System.out.println(gcd(100,15));
	System.out.println(gcd(100,10));
	System.out.println(gcd(120,30));
	System.out.println(gcd(140,7));
	System.out.println(gcd(181,11));
}