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

윤설안

Feb 06, 2025

Contents

유클리드 호제법(비지니스 파악)공식 적용 클래스를 이용하여 출력

💡

두 자연수의 공통된 약수 중 가장 큰 수

문제

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

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

공식 적용


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);
    }
}

두 수 a과 b가 있을 때, a과 b의 약수 집합이 공통으로 갖는 수 중 가장 큰 수가 최대공약수이다.

따라서 a과 b의 모든 약수 집합을 돌면서 같은 수가 나올 때 마다 gcd값과 비교하여 더 클 경우 c에 갱신해준다.

클래스를 이용하여 출력



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));
    }
}

Contents

유클리드 호제법(비지니스 파악)공식 적용 클래스를 이용하여 출력

JAVA 알고리즘

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

윤설안

Feb 06, 2025

Contents

유클리드 호제법(비지니스 파악)공식 적용 클래스를 이용하여 출력

💡

두 자연수의 공통된 약수 중 가장 큰 수

문제

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

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

공식 적용


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);
    }
}

두 수 a과 b가 있을 때, a과 b의 약수 집합이 공통으로 갖는 수 중 가장 큰 수가 최대공약수이다.

따라서 a과 b의 모든 약수 집합을 돌면서 같은 수가 나올 때 마다 gcd값과 비교하여 더 클 경우 c에 갱신해준다.

클래스를 이용하여 출력



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));
    }
}

Contents

유클리드 호제법(비지니스 파악)공식 적용 클래스를 이용하여 출력