유클리드 호제법 JAVA

두 양의 정수 혹은 두 다항식의 최대공약수를 구하는 방법.

작은 수를 a, 큰 수를 b라 하고 b는 a로 나누어 떨어지지 않는다면

b = a * q + r 로 나타낼 수 있다(q : 몫, r : 나머지)

이 때 나눈 수인 a는 나머지인 r보다 크므로 a를 r로 나눌 수 있게 되는데,

a = r * q' + r'으로 나타낼 수 있고 이는

b = (r * q' + r') * q + r 이 된다. 만약 여기서 r' = 0 이라면 b = (r * q') * q + r 로 나타내어

a 와 b 모두 r을 인수로 갖고 있음을 알 수 있는데  이 규칙대로 숫자를 계속해서 나눈다면

마지막 나머지가 0 이 됐을 때 전체 숫자는 나눈 수를 인수로 갖게 되므로 그 수가 최대공약수가 된다.

 

예시 코드)

public class MaxCommon {
	public static void main(String[] args) {
		int a = 78696;
	    int b = 19332;
	    int commonNum = common(a, b);
	    System.out.println("최대공약수 : "+commonNum);
	}

	public static int common(int a, int b) {
	    int min = Math.min(a, b);
	    int max = Math.max(a, b);
	    while(min!=0) {
	        int rest = max%min;	//큰 수를 작은수로 나눈 나머지
	        max = min;	//나눈 수(작은 수)가 나뉘어질 수가 됨
	        min = rest;	//나머지가 나눌 수가 됨
	    }	
	    return max;		//나머지가 0이 되면 나눈 수 반환
	}
}