[JAVA] 최대공약수, 최소공배수 찾기

가장 기초적인 방식으로 최대공약수를 구하는 방법은 큰 수부터 차례대로 나누는 것이고, 최소 공배수는 두 수 중 작은 수부터 시작해 동시에 나누어지는 수를 검사하는 방식이다.

 

하지만 이러한 방법은 두 수가 모두 소수이면 오랜 시간이 소모될 수 있다.

그래서 최대공약수와 최소공배수를 효율적으로 구하기 위해 유클리드 호제법을 사용할 수 있다.

int uclid(int a, int b) 
{
	if (b==0) return a;
   	return uclid(b, a%b);
}

 

추가로 간혹 유클리드 호제법을 사용해도 풀리지 않는 알고리즘 문제들이 존재한다.

이럴 때는 확장 유클리드 호제법을 사용하면 된다.

int extUclid(int a, int b, Integer[] x, Integer[] y) 
{
 	int g = a;
   	x[0] = 1;
   	y[0] = 0;
   	
   	if (b!=0) {
   		g = extUclid(b, a%b, y, x);
   		y[0] -= (a/b) * x[0];
   	}
    
   	return g;
}