수학 / 백준 2609 최대공약수와 최소공배수

 

문제 접근

최대공약수는 유클리드 호제법으로 구함

1. 두 수 중 큰 수를 작은 수로 나눔
2. 나머지가 0이 될 때까지 나머지를 다음 나눗셈의 나누는 수로 사용하여 계속 나눔
3. 나머지가 0이 되었을 때 나눈 수가 최대공약수

 

최소공배수는 두 수를 곱한 값을 최대공약수로 나눠서 구함

 

>> 최대공약수만 구하면 끝

풀이

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

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

        String[] split = br.readLine().split(" ");

        int A = Integer.parseInt(split[0]);
        int B = Integer.parseInt(split[1]);

        int gcd;

        if (A < B) {
            gcd = gcd(B, A);
        } else {
            gcd = gcd(A, B);
        }

        int lcm = A * B / gcd;

        sb.append(gcd).append("\n");
        sb.append(lcm).append("\n");

        System.out.println(sb);
    }

    public static int gcd(int A, int B){
        if (B == 0) {
            return A;
        }
        return gcd(B, A % B);
    }
}