[백준 #5347] LCM(최소공배수) 문제

---

https://www.acmicpc.net/problem/5347

 

1. 문제

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

 

출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.

 

예제 입력

3
15 21
33 22
9 10

 

예제 출력

105
66
90

 

해결 코드

GCD를 효율적으로 구할 수 있다면 LCM은 손쉽게 구할 수 있다.

import java.util.Scanner;

public class Main {

    public static long GCD(long m, long n) {

        while(n != 0) {
            long temp = m;
            m = n;
            n = temp % n;
        }

        return m;
    }

    public static long LCM(long m, long n) {
        long gcd = GCD(m, n);
        return (m / gcd) * (n / gcd) * gcd;
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        for(int i=0; i<n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            long lcm = LCM(a, b);

            System.out.println(lcm);
        }
    }
    
}