(3) [C++, Java] 백준 No.1934 : 최소공배수

문제

풀이

자세한 풀이 : 

 

-  A, B는 1 ~ 45,000 이므로 둘 다 최대로 45,000 일 때 A x B = 2,025,000,000 (20억) 이므로
   int형의 저장범위를 벗어나지 않기 때문에 자료형은 크게 신경쓰지 않아도 된다.

 

# C++

#include <iostream>

using namespace std;

int getGCD(int a, int b)
{
    if (b == 0)
        return a;
    else
        return getGCD(b, a%b);
}

int main()
{
    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++)
    {
        int a, b;
        cin >> a >> b;

        int gcd = getGCD(a, b); // 최대공약수 : 유클리드 호제법 사용
        int lcm = a*b/gcd;      // 최소공배수 : gcd x lcm = A x B 이용

        cout << lcm << endl;
    }
}

# Java

import java.util.*;

public class Main {
    public static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x%y);
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int g = gcd(a, b);
            int l = a * b / g;
            System.out.println(l);
        }
    }
}