최대공약수(Greatest Common Divisor)를 언어로 구현하기

1. 최대공약수

• Greatest Common Divisor
• 공약수는 정수 i의 약수이자 정수 j의 약수이다.
• 최대공약수는 공약수 중 가장 큰 값이다.

---

2. 구현

2-1. 유클리드 호제법

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

다음은 유클리드 호제법을 이용하여 최대공약수를 구하는 자바 코드이다.

public class GreatestCommonDivisor {
	public static void main(String[] args) {
		int i = 663;
		int j = 2427;

		GreatestCommonDivisor gcd = new GreatestCommonDivisor();

		int result = 0;
		
		if (i > j)
			result = gcd.get(i, j);
		else
			result = gcd.get(j, i);

		System.out.println("gcd="+result);
	}

	int get(int i, int j) {
		if (j == 0)
			return i;
		else
			return get(j, i % j);
	}
}