[Java] 30. 최대 공약수 알고리즘

4의 약수: 1, 2, 4
24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
공통 약수: 1, 2, 4
최대 공약수 : 4

1. 4와 24의 약수 구하기

package algo;

public class GCD {
    public static void main(String[] args) {
        // 4와 24의 최대공약수를 구하시오.

        //1. 4의 약수를 구한다.
        int a = 0;
        int b = 4;

        for (int i = 1; i < 5; i++) {
            a++;
            if (b % a == 0) {
                System.out.println(a + "는 " + b + "의 약수");
            }
        }

        System.out.println("====================");

        // 2. 24의 약수를 구한다.
        int c = 0;
        int d = 24;

        for (int i = 1; i < 25; i++) {
            c++;
            if (d % c == 0) {
                System.out.println(c + "는 " + d + "의 약수");
            }
        }
    }
}

2. 4와 24의 최대 공약수 구하기

package algo;

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

        int a = 24; // 비교할 두 수 입력
        int b = 4; // 비교할 두 수 입력

        while (true) {
            int c = a % b; // 첫바퀴 : a % b = 6 // 두바퀴 : a % b = 0
            a = b; // 첫바퀴 : b = 12 // 두바퀴 : b = 6
            b = c; // 첫바퀴 : c = 6 // 두바퀴 : c = 0

            if (c == 0) { // 첫바퀴 : c = 6 (조건에 맞지 않음) // 두바퀴 c = 0 (조건에 맞음)

                break; // 두바퀴 시 조건에 맞기 때문에 break문을 통해 while을 빠져나감.
            }
        }
        System.out.println("최대 공약수는 : " + a); // 결과 출력
    }
}