유클리드호제법

유클리드호제법을 사용하여 최대공약수를 찾는 알고리즘은 다음과 같다.

pubic int getCommon(int a, intb){
	int n=0;
    while(b!=0){
    	n = a%b;
        a = b;
        b = n;
    }
    
    return a;
}

이 알고리즘은 a>b일 때 둘을 나누면서 최대 공약수를 찾는 방식이다.

이렇게 직접 알고리즘을 구현해도 되고 BigInteger의 메소드를 사용하는 방법도 있으며 그 방식은 아래와 같다.

public int getCommon(int a, int b){
        BigInteger num1 = BigInteger.valueOf(a);
        BigInteger num2 = BigInteger.valueOf(b);
        BigInteger gcd = num1.gcd(num2);
        return gcd.intValue();
}