1934 최소공배수

BOJ::1934 최소공배수

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

최소공배수 구하는 문제.

유클리드 호제법을 이용하면 쉽게 정답을 구할 수 있다.

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            System.out.println((x*y)/getGcd(x,y));
        }
    }
    
    //최대공약수 구하기
    public static int getGcd(int x,int y){
        if(y>x){
            int tmp=x;
            x=y;
            y=tmp;
        }
        while(x%y!=0){
            int t = x%y;
            x=y;
            y=t;
        }
        return y;
    }
}
 

<C++>

#include <iostream>
using namespace std;
 
int n;
 
int getGcd(int x, int y) {
    if (y > x) {
        int tmp = x;
        x = y;
        y = tmp;
    }
    while (x%y != 0) {
        int t = x % y;
        x = y;
        y = t;
    }
    return y;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        cout << (x*y) / getGcd(x, y) << endl;
    }
}