[백준] java 1934 최소공배수

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

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

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

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

풀이과정

최소 공배수를 구하는 방법은 여러가지가 있지만 나는 다음과 같은 방법을 사용하였다. 정수 A, B에 대해서 서로소가 나오기 전까지 계속 나눈다.

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());

		for( int i = 0; i < T; i++ ){
			st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int sum = 1;

			for(int j = 2; j <= (Math.min(A, B)); j++ ){

				if( A % j == 0 && B % j == 0 ){
					A /= j; B /= j;
					sum *= j;
					j = 1;
				}

			}
			sb.append(A*B*sum).append("\n");
		}
		System.out.println(sb);
	}

아래의 반복문으로 나눌 때 사용했던 정수와 서로소를 곱하면 최소 공배수를 구할 수 있다.
if( A % j == 0 && B % j == 0 ) 제어문을 통해 공약수가 있을 때만 나누게끔 하였다. 공약수가 없다면 서로소이므로 바로 곱해주면 된다.

for(int j = 2; j <= (Math.min(A, B)); j++ ){

	if( A % j == 0 && B % j == 0 ){
		A /= j; B /= j;
		sum *= j;
		j = 1;
	}
    
}