백준 2609 문제를 풀다가, 문제를 해결하기 위해서는 유클리드 호제법을 알아야 해서 정리하였다.

유클리드 호제법

• 큰 두 수가 있을 때 최대공약수를 구하기 위해 사용된다.
• 2개 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.
• A를 B로 나눈 나머지를 r이라고 하면 (A>B, A와 B의 최대공약수는 B와 r의 최대공약수와 같다.
• 유클리디안 호제법, 호제법, Euclid GCD 라고도 불리운다.

최대공약수 (GCD : Greatest Common Divisor)

두 수 이상의 여러 수의 공약수 중 최대인 수

풀이 방법

1. 매개변수로 a,b를 받는다. 단, a > b
2. b가 0이라면, a가 최대공약수
3. b가 0이 아니라면, 1번 매개변수에 ‘b’와 ‘a%b’를 전달한다.
4. 위 내용을 반복한다.

풀어가는 과정

몫은 필요없다. 나머지가 중요하다

큰 수 / 작은 수 = 몫... 나머지
작은 수 / 나머지 = 몫 ... 나머지
나머지/ 그 다음 나머지 = 몫 ... 나머지
그 다음 나머지 / 그 다음 나머지 = 몫... $0$

나머지가 $0$ 이 될 때 나뉘어진 수가 최대 공약수가 된다!

예시

$146$과 $64$의 최대공약수는

$146 / 64 = 2$ (몫) $...18$ (나머지)
$64 / 18 = 3...10$
$18 / 10 = 1...8$
$10 / 8 = 1...2$
$8 /$ $2$ = $4...$ $0$

나머지가 0이 될 때의 나뉘었던, 2가 최대 공약수가 된다!
→ $GCD =$ $2$

Code

public class EuclidGCD {

    private static int euclidGCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        return euclidGCD(b, a % b);
    }

    public static void main(String[] args) {
        // 전제 : a > b
        int a = 90;
        int b = 24;

        System.out.println(a + "와 " + b + "의 최대공약수 : " + euclidGCD(a, b));


        // 다른 방법
        int temp;

        while (b != 0) {
            temp = b;
            b = a % b;
            a = temp;
        }

        System.out.println("위 결과와 같은지? 답 : " + a);
    }

}

코드를 실행하면, 재귀호출 방법과 while 문을 이용한 방법 모두 결과가 $6$으로 동일하다.
즉, $90$과 $24$의 최대공약수는 $6$

최소공배수 (LCM : Least Common Multiple / Lowest Common Multiple)

두 수 이상의 여러 수의 공배수 중 최소인 수

최소공배수
= 정수 정수 / 최대공약수
= a b / c

Code (백준 2609 최대공약수와 최대공배수)

최소공배수를 먼저 구해준 후, 구해진 최소공배수와 입력받은 a, b를 모두 곱한다.

import java.util.Scanner;
//최대공약수와 최소공배수
public class Main{
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int a = in.nextInt();
        int b = in.nextInt();

        int d = gcd(a, b);	// 최대공약수
        int m = lcm(a, b);  // 최대공배수

        System.out.println(d);
        System.out.println(m);
        //System.out.println(a*b/c); 최대공배수 함수를 호출하지 않고 바로 구하기

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

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

참고
어라운드허브 스튜디오 - [자바로 배우는 자료구조] 유클리드호제법
스크래치로 배우는 알고리즘 - 유클리드 호제법