자바(Java) 두 수에서 최대공약수 찾는 방법, BigInteger

자바(Java) 두 수에서 최대공약수 찾는 방법, BigInteger

 

환경 : Eclipse Mars, JDK 1.7

 

최대공약수는 두 수의 공통 약수중 최대값을 말합니다. 약수는 나누어서 0 이 되는 수를 말하죠. 이렇게 나누어서 0 이 되는 수중 공통적으로 들어가 있으며, 최대값을 찾는 것입니다. 자바에서는 BigInteger 클래스에 최대공약수를 구할수 있는 gcd() 함수를 제공합니다. 함수를 이용해서 구하는 방법과 직접 함수를 만드는 방법에 대해 알아 보겠습니다.

 

▼ 최대공약수는 BigInteger 클래스 함수중 gcd() 를 이용하시면 바로 구할수 있습니다. 값을 BigInteger 로 캐스팅한후 첫번째 BigInteger 객체의 gcd() 함수 인수로 두 번째 숫자의 BigInteger 객체를 넘기면 됩니다. 

private static int gcdThing(int a, int b) {
	BigInteger b1 = BigInteger.valueOf(a);
	BigInteger b2 = BigInteger.valueOf(b);
	BigInteger gcd = b1.gcd(b2);
	return gcd.intValue();
}

 

▼ 최대공약수를 구하는 방법중 호제법이라는 것이 있습니다. 두수를 나누어서 나온 나머지를 이전 나머지에 다시 나눕니다. 그렇게 0 이 나올 때 까지 반복한후 중지 합니다. 바로 직전 나머지가 최대공약수가 되는 것이죠. 예를 들어 192 와 72 의 최대공약수를 구한다고 합시다. 아래 처럼 3번째 단계가 되면 나머지가 0 이죠. 그때 이전 몫인 24가 최대공약수가 되는 것입니다.

 

1. 192 = 72 x 2 + 48

2. 72 = 48 x 1 + 24

3. 48 = 24 x 2 + 0

 

아래 함수는 호제법을 구현한 것입니다. 재귀호출을 사용해서 b 가 0 이 될때까지 반복하게 되는 것이죠. 

// 함수를 사용하지 호제법 알고리즘으로 직접 구현 
private static int GCD(int a, int b) {
	if (b == 0){
		return a;
	}
	return GCD(b, a % b);
}

 

▼ 아래는 두 함수를 이용해서 최대공약수를 구하는 전체소스 입니다.

import java.math.BigInteger;

public class Gcd {
	public static void main(String[] args) {

		// 최대공약수 구하기
		int gcdValue = gcdThing(192, 72);
		System.out.println("1. BigInteger.gcd() 함수이용, 최대공약수 : " + gcdValue);
		System.out.println("2. 호제법 최대공약수 : " + GCD(192, 72));
	}

	private static int gcdThing(int a, int b) {
		BigInteger b1 = BigInteger.valueOf(a);
		BigInteger b2 = BigInteger.valueOf(b);
		BigInteger gcd = b1.gcd(b2);
		return gcd.intValue();
	}
	
	// 함수를 사용하지 호제법 알고리즘으로 직접 구현 
	private static int GCD(int a, int b) {
		if (b == 0){
			return a;
		}
		return GCD(b, a % b);
	}
}

// 결과 
1. gcd() 함수이용, 최대공약수 : 24
2. 최대공약수 : 24