Today I Learned

오늘은 간만에 휴식하기 전 가끔씩 봤던 최소 공배수, 최대 공약수 문제를 간단하게 풀 수 있는 유클리드 호제법에 대해 정리해보려 한다.

유클리드 호제법(Euclidean Algorithm)

두 정수의 최대공약수(GCD)를 찾는 효율적인 알고리즘

• GCD : Greatest Common Divisor, 두 수의 공통된 약수 중 가장 큰 수.

• LCM : Least Common Multiple, 두 수의 공통된 배수 중 가장 작은 수.

• 과정

두 수 a, b(a>b)의 최대 공약수는 r(=a%b, a를 b로 나눈 나머지)과 b의 최대공약수와 동일하다.
즉, GCD(a,b) = GCD(b,r)
해당 과정을 반복해서 r이 0이 되면, 그 때의 b가 최대 공약수다.

큰 수를 작은 수로 반복적으로 나눠 나머지가 0이 될 때까지 작동해 그때의 작은 수가 최대 공약수

구현

• 재귀

  public static int gcdRecursion(int a, int b){
    if (b==0) return a;
    return gcdRecursion(b,a%b);
  }

• 반복문

  public static int gcdLoop(int a, int b){
    while (b != 0){
      int tmp = b;
      b = a%b;
      a = tmp;
    }
    return a;
  }

최소 공배수(LCM)

최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같다.

• LCM(a,b) = a * b / GCD(a,b)

  public static int lcm(int a, int b){
    return a * b / gcdLoop(a,b);
  }

최종 코드

package p1;

import java.util.Scanner;

public class A_Euclidean {

  // 반복문
  public static int gcdLoop(int a, int b){
    while (b != 0){
      int tmp = b;
      b = a%b;
      a = tmp;
    }
    return a;
  }

  // 재귀
  public static int gcdRecursion(int a, int b){
    if (b==0) return a;
    return gcdRecursion(b,a%b);
  }

  public static int lcm(int a, int b){
    return a * b / gcdLoop(a,b);
  }

  public static void main(String[] args) {
    System.out.println("최대 공약수와 최소공배수를 구할 두 정수를 입력해주세요.");
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();

    if(a<1 || b<1) throw new RuntimeException("양의 정수를 입력하세요.");

    // a<b면 스왑.
    if(a<b) {
      int tmp = a;
      a = b;
      b = tmp;
    }


    int answer1 = gcdLoop(a,b);
    int answer2 = gcdRecursion(a,b);
    int answer3 = lcm(a,b);

    System.out.println("반복문으로 구한 두 수의 최대 공약수는 " + answer1);
    System.out.println("재귀로 구한 두 수의 최대 공약수는 " + answer2);
    System.out.println("두 수의 최소 공배수는 " + answer3);


  }

}