백준 1934번 최소공배수

주어진 두 숫자의 최소공배수를 구하는 문제다.

 

이 문제는 두 숫자의 최대공약수를 구하는 대표적인 알고리즘인 유클리드 호제법을 활용해 풀이하였다.

 

※ 최소공배수를 구하는 문제이며, 최소공배수는 [숫자1 x 숫자2 / 최대공약수] 로 계산할 수 있다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int T = in.nextInt();

        for (int i = 0; i < T; i++) {
            int A = in.nextInt();
            int B = in.nextInt();

            int gcd = calcGcd(B, A); // 최대공약수
            int lcm = A * B / gcd; // 최소공배수
            System.out.println(lcm);
        }
    }

    public static int calcGcd(int big, int small) {
        if (big % small == 0) {
            return small;
        }
        return calcGcd(small, big % small);
    }
}