최소 공약수

01 Sep 2023 in Algorithm on Java, Coding, Test

• 참고 : 유클리드 호제법
• 유클리드 호제법을 이용하여 최대 공약수를 구한다.
• 큰 수를 작은 수로 나눈 나머지를 0이 될 때까지 수행하여 최대 공약수를 구한다.

자바 소스

/**
 * 최대 공약수 구하기.
 * 유클리드 호제법을 이용한 최대 공약수 구하기
 * 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될때까지 작동하여 최대공약수를 구한다.
 *
 * @author chiptune
 * @since 2023.09.01
 */
public class GCD {

    /**
     * 재귀 방식
     * 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복 하여 큰 수를 리턴한다.
     */
    public static int recursion(int a, int b) {
        if (b == 0) return a;
        return recursion(b, a % b);
    }

    /**
     * 반복문 방식
     * b에 a에서 b를 나눈 나머지를 계속 반복 저장하여 0이 될 때 까지 수행 후, 큰 수를 리턴한다.
     */
    public static int repeat(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

최대 공배수

• 유클리드 호제법에 따라 최대 공약수를 구한 후, 두 수를 곱한 값에서 나눈다.

자바 소스

/**
 * 최소 공배수 구하기
 * 두 수의 배수가 되는 값 중, 최소 값을 구하는 방법.
 * 유클리드 호제법에 따라 최대 공약수를 구한 후, 두 수를 곱한 값에서 나눈다.
 *
 * @author chiptune
 * @since 2023.09.01
 */
public class LCM {

    // 최소공배수 = 두 수의 곱 / 최대공약수
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    private static int gcd(int a, int b) {
        // 재귀
        if (b == 0) return a;
        return gcd(b, a % b);
        // 반복
        //        while (b != 0) {
        //            int temp = b;
        //            b = a % b;
        //            a = temp;
        //        }
        //        return a;
    }
}

테스트 해보기

public class Test {
    public static void main(String[] args) {
        // what is GCD of 10,5 ?
        System.out.println(GCD.recursion(10, 5)); // 5
        // what is LCM of 10,5 ?
        System.out.println(LCM.lcm(10, 5)); // 10
    }
}