유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 빠르게 구하는 알고리즘이다.

최대공약수(GCD)	A를 B로 나눈 몫을 𝑄라 하고, 나머지를 𝑅이라 할때, gcd(A,B)=gcd(B,R)이다.
최소공배수(LCM)	A와 B라는 다른 수가 주어졌을때, 주어진 두 개의 수를 곱한 값을 GCD로 나눈 값이다.

 

조금 머리가 아프다...

수능에는 안 나오지만 컴퓨터 공학를 이용한 계산에 쓰이는 정수론에 가장 많이 쓰인다고 한다.

자세한 글과 증명법은 https://dimenchoi.tistory.com/46 을 참고하면 좋다.

 

중학수학에서 두 수 사이의 최대공약수는 소인수분해를 한 후

그 소인수들의 곱으로 구할 수 있었지만

효율적인 방법은 아니다.

 

왜냐하면 우선 소인수분해를 위해 소수를 먼저 찾아야 하고

찾은 소수가 두 개의 수를 나눌 수 있는지 확인을 하는 절차를 거쳐야 하기 때문에

수가 크면 계산이 복잡해지는 단점이 있기 때문에 이를 보완하기 위해 나온 방법이다.

 

자바 코드로 살펴보겠다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class LCMCalculator {

       public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 사용자로부터 첫 번째 정수 입력 받기
        System.out.print("첫 번째 정수를 입력하세요: ");
        int a = Integer.parseInt(br.readLine());

        // 사용자로부터 두 번째 정수 입력 받기
        System.out.print("두 번째 정수를 입력하세요: ");
        int b = Integer.parseInt(br.readLine());

        // 최대공약수 계산
        int gcd = findGCD(a, b);

        // 최소공배수 계산
        int lcm = findLCM(a, b, gcd);

        System.out.println("두 정수의 최대공약수는 " + gcd + "입니다.");
        System.out.println("두 정수의 최소공배수는 " + lcm + "입니다.");
        br.close();
    }

    /**
     * 두 정수의 최대공약수(GCD)를 구하는 함수
     * @param a 첫 번째 정수
     * @param b 두 번째 정수
     * @return a와 b의 최대공약수
     */
    public static int findGCD(int a, int b) {
        // 유클리드 호제법을 사용하여 최대공약수 구하기
      // a와 b 중에서 큰 값을 a로, 작은 값을 b로 설정하여 시작
        while (b != 0) {
            int temp = b; // b를 임시 변수 temp에 저장
            b = a % b;    // a를 b로 나눈 나머지를 b에 저장 (나머지 연산)
            a = temp;     // temp에 저장된 값을 a에 대입하여 반복
        }
        return a; // b가 0이 되면 반복문을 종료하고 a가 최대공약수가 됨
    }

    /**
     * 두 정수의 최소공배수(LCM)를 구하는 함수
     * @param a 첫 번째 정수
     * @param b 두 번째 정수
     * @param gcd a와 b의 최대공약수
     * @return a와 b의 최소공배수
     */
    public static int findLCM(int a, int b, int gcd) {
        // 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같다
        return (a * b) / gcd;
    }
}