[알고리즘] 유클리드 호제법

Dev_An_Student·2025년 1월 7일

알고리즘 유클리드 호제법 최대공약수 최소공배수

알고리즘

목록 보기

2/5

유클리드 호제법의 원리

두 수 A와 B의 최대공약수는 A % B(A를 B로 나눈 나머지)와 B의 최대공약수와 같다는 것을 이용한다.
이 과정을 반복해서 B = 0이 되면, 그 때의 A가 두 수의 최대공약수이다.

예시

A = 56, B = 42의 최대공약수를 구해야 한다.

A % B를 구한다:
- 56 % 42 = 14(56을 42로 나누면 나머지는 14이다.)
이제 A = B, B = A % B로 초기화 한다.
- A = 42, B = 12가 된다.
다시 나머지를 구한다.
- 42 % 14 = 0
B = 0이 되었으므로, 현재의 A = 14가 최대 공약수가 된다.

public static int gcd(int a, int b) {
    while (b != 0) { // 나머지가 0이 될 때까지 반복
        int temp = b;  // 현재 b를 저장
        b = a % b;     // a를 b로 나눈 나머지로 b를 업데이트
        a = temp;      // a는 이전 b로 업데이트
    }
    return a; // 마지막에 남은 a가 최대공약수
}

요약

큰 수를 작은 수로 나누고, 나머지를 구한다.
작은 수를 다시 큰 수로 설정하고 나머지를 작은 수로 설정한다.
다시 큰 수에서 작은 수를 나누고, 나머지를 구한다.
나머지가 0이 될 때까지 2 - 3의 과정을 반복한다.
나머지가 0일 때, 마지막에 남은 큰 수가 최대공약수가 된다.

최소공배수

유클리드 호제법을 사용하여 최소공배수를 구할 수 있다.

최소공배수와 최대공약수의 관계

두 수 A와 B에 대해, 최소공배수는 다음과 같다.

A와 B의 최소공배수 = A x B % A와 B의 최대공약수

why?

A와 B의 곱은 A와 B의 모든 공통 약수와 서로소 관계인 수를 포함한다.
최대공약수로 나눠주면 공통된 부분을 제거하여 최소공배수를 얻을 수 있다.

예시

A = 56, B = 42의 최소공배수 구해야 한다.

A % B를 구한다:
- 56 % 42 = 14(56을 42로 나누면 나머지는 14이다.)
이제 A = B, B = A % B로 초기화 한다.
- A = 42, B = 12가 된다.
다시 나머지를 구한다.
- 42 % 14 = 0
B = 0이 되었으므로, 현재의 A = 14가 최대 공약수가 된다.
A * B를 구한다.
- 56 * 42 = 2352
2352를 최대공약수인 14로 나눈다.
- 2352 / 14 = 168
A와 B의 최소공배수는 168이 된다.

import java.util.Scanner;

public class Main {
    // 최대공약수(GCD) 계산 (유클리드 호제법 사용)
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 최소공배수(LCM) 계산
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b); // 두 수의 곱을 최대공약수로 나눔
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter two numbers: ");
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 출력
        System.out.println("GCD: " + gcd(n, m));
        System.out.println("LCM: " + lcm(n, m));
    }
}