[JAVA-알고리즘] 4. 최대공약수(GCD)

유클리드 호제법(비지니스 파악)

공식 적용

package algo;

public class Gcd01 {
    public static void main(String[] args) {

        // gcd(a,b) = gcd(b, a % b)

        // 12와 18의 최대공약수
        // 18(a) % 12(b) = 6(c)
        // 12(a) % 6(b) = 0(c)
        // 최대공약수는 6

        int a = 52;
        int b = 18;
        int c = 0;
        int div = 1;

        // 1번 나눔
        while (true) {
            System.out.println(div + "번 째 나누기");
            c = a % b; // 6 = 18 % 12
            a = b; // a = 12
            b = c; // b = 6
            System.out.println(a);
            if (c == 0) {
                break;
            }
            div++;
        }
        System.out.println("두 수의 최대공약수는 : " + a);
    }
}

클래스를 이용하여 출력

package algo;

public class Gcd04 {
    static int gcd(int a, int b) {
        while (true) {
            int c = a % b; // 6 = 18 % 12
            a = b; // a = 12
            b = c; // b = 6
            if (c == 0) {
                break;
            }
        }
        return a;
    }

    public static void main(String[] args) {
        int a = 52;
        int b = 18;
        System.out.println("두 수의 최대공약수는 : " + gcd(a, b));
    }
}