[알고리즘] 유클리드 호제법

유클리드 호제법이란?

A를 B로(A > B) 나눈 나머지를 r이라고 할 때, A와 B의 최대공약수는 B와 r의 최대공약수와 같다.

알고리즘

1. 매개변수로 A와 B를 받는다. (단, A > B)
2. B가 0이라면, A가 최대공약수
3. B가 0이 아니라면, 1번의 매개변수에 B와 A%B를 전달한다.
4. 위의 내용을 반복한다.

예시

90과 24의 최대공약수는?
1. 90%24 -> 18
2. 24%18 -> 6
3. 18%6 -> 0
최대공약수 = 6

코드

1. 재귀

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

2. while

public int GCD(int a, int b) {
	int tmp;

	while(b != 0) {
      tmp = b;
      b = a % b;
      a = tmp;
	}
    
	return a;
}

최대공약수로 최소공배수 구하기

두 수의 곱에 최대 공약수를 나눈 값과 같다.

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}