Baekjoon 5347 LCM JAVA

5347번: LCM

문제

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

입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.

풀이

유클리드 호제법을 이용하여 최대공약수를 계산하여 준다.

최대 공약수가 있다면 최소공약수는 "주어지는 값1 * 주어지는 값2 / 최대공약수"이다

 

위의 공식을 사용할때 최대공약수가 존재하지 않는다면 Division by Zero가 발생하기에 최대공약수를 1로 만들어준다.

코드

import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		for(int i=0;i<n;i++) {
			long a=sc.nextLong(), b=sc.nextLong();
			long c=gcd(a,b);
			if(c==0)	// 최대 공약수가 존재하지 않으면 0으로 되고 값은 0으로 나눌수 없기에 1을 대입
				c=1;
			System.out.println(a*b/c);
		}
	}
	public static long gcd(long a, long b) {	// 최대공약수 계산
		if(a<b) {
			long t=a;
			a=b;
			b=t;
		}
		while(b>0) {	// 유클리드 호제법을 이용하여 최대공약수를 계산
			a=a%b;
			if(a<b) {
				long t=a;
				a=b;
				b=t;
			}
		}
		return a;
	}
}