유클리드 호제법을 이용한 두 수의 최대공약수 구하기

설명

두 자연수 a, b에 대하여 두 수의 최대 공약수는 다음과 같이 구할 수 있다.

1. a를 b 로 나눈다.
2. a 가 b로 나누어 떨어지지 않는다면, a는 b가 되고, b는 a%b가 된다.
3. 1번으로 돌아가서 a가 b로 나누어 떨어질 때까지 반복한다.
4. a가 b가 b로 나누어 떨어질 때, b가 최대 공약수(gcd)가 된다.
5. 초기값 a 와 초기값 b를 곱한 수에 gcd를 나누면 최소 공배수(lcm)이 구해진다

=> 이를 유클리드 호제법이라 한다.

 

Java 코드

public static int gcd(int a, int b){
        while(b!=0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }