본문 바로가기
Algorithm/Baekjoon

Baekjoon 5347 LCM JAVA

by Hunveloper 2022. 9. 18.
728x90

 

5347번: LCM

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

www.acmicpc.net

문제

두 수 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;
}
}
728x90
728x90

댓글