[Algorithm] 유클리드 호제법

̱ 유클리드 호제법

 

유클리드 호제법은 두 정수의 최대공약수를 재귀적으로 구하는 방법입니다.

여기서 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘입니다.

두 정수가 주어지면 큰 값을 작은 값으로 나누었을 때 나누어 떨어지는 가장 작은 값이 최대공약수입니다.

나누어지지 않으면 작은 값(얻은 나머지)에 대해 나누어 떨어질 때까지 같은 과정을 재귀적으로 반복합니다.

이 과정을 좀 더 수학적으로 표현하자면 두 정수 x, y 의 최대공약수를 gcd(x, y) 로 표기하겠습니다.

x = az 와 y = bz 를 만족하는 정수 a, b 와 최대의 정수 z 가 존재할 때 z 를 gcd(x, y) 라고 할 수 있습니다

이렇게 되면 a 와 b 는 서로소가 됩니다.

최대공약수 y 가 0이라면 x 이고 , y 가 0이 아니면 gcd(y,  x%y) 로 구합니다.

아래는 유클리드 호제법으로 최대공약수를 구하는 코드입니다.

 

public class EuclidGCDTest {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        System.out.println(gcd(x,y));
    }
    public static int gcd(int x, int y) {

        if(y == 0)
            return x;
        else {
            return gcd(y, x%y);
        }
    }
}

 

 

숫자 순서를 바꿔 8 22 를 입력해도 결과는 똑같이 출력됩니다.

여기서 만약 최소공배수를 알고싶다면  x * y * 최대공약수 로 구할 수 있습니다.