[백준-1934번/Java] 최소공배수

* 유클리드 호제법

두 양의 정수 a, b (a>b)에 대하여 a=bq+r이라 하면, (a, b)의 최대공약수는 (b,r)의 최대공약수와 같다.
r==0 일 때, 두 수의 최대공약수는 b이다.
최소 공배수 = a * b / 최대공약수

* 최대공약수

* 최소공배수

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(stk.nextToken());
			int b = Integer.parseInt(stk.nextToken());
			System.out.println(lcm(a, b));

		}

	}

	private static int gcd(int a, int b) {
		int temp;
		if (a < b) {
			temp = a;
			a = b;
			b = temp;
		}
		int r = a % b;
		if (r == 0) {
			return b;
		}
		return gcd(b, r);
	}

	private static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}

}