[유클리드 호제법] / [백준(baekjoon) 1934] 최소공배수(LCM)

문제

백준 1934

최소공배수(LCM) 를 구하시오.

원리

최소공배수(LCM)

A,B의 최소공배수 = A * (B/최대공약수)

• 최대공약수 : 유클리드 호제법 사용

유클리드 호제법, GCM, LCD 설명 포스트 참고!

구현 java

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.        for (int i = 0; i < n; i++) {
8.            int a = sc.nextInt();
9.            int b = sc.nextInt();
10.
11.            int gcd = gcd(a, b);
12.            System.out.println(a * (b / gcd));
13.        }
14.    }
15.
16.    static int gcd (int a, int b) {
17.        int r = a % b;
18.        if (r == 0) return b;
19.        return gcd(b, r);
20.    }
21.}

결과