[Coding Test] inflearn(10)

1. 유클리드 호제법 (Euclidean Algorithm)

두 수의 '최대공약수(GCD)'를 찾기 위한 알고리즘을 의미한다.

큰 수를 작은 수로 나누어 떨어지게 한 뒤, 수를 반복적으로 수행하여 나머지 0이 될때까지 작동한느 방법을 의미한다. 이 때 작은 수가 최대공약수이다.

2. 최대공약수(GCD) & 최소공배수(LCM)

• 최대공약수(GCD) : 두 수의 공통된 '약수 중에서 가장 큰 수'를 의미한다.
• 최소공배수(LCM) : 두 수의 공통된 '배수 중에서 가장 작은 수'를 의미한다.

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

숫자 a, b가 있고 최대공약수 gcd, 최소공배수 lcm이 있으면
ab = gcd lcm 식이 성립한다.

최소공배수(LCM) = a*b / GCD

3. 유클리드 호제법 실전 문제

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

import java.util.Scanner;

public class P2609_최대공약수와최소공배수 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v1 = sc.nextInt();
        int v2 = sc.nextInt();
        int gcd = GCD(v1, v2);
        int LCM = v1 * v2 / gcd;
        System.out.println(gcd);
        System.out.println(LCM);
    }

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