두 자연수 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)
첫째 줄부터 T
개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.
3
1 45000
6 10
13 17
45000
30
221
-문제의 오타를 찾은 사람: jason9319, kyo20111
import java.io.*;
public class Code1934 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.valueOf(br.readLine());
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
for(int i=0;i<T;i++){
String[] nums=br.readLine().split(" ");
int A=Integer.valueOf(nums[0]);
int B=Integer.valueOf(nums[1]);
int small=0;
int divisor=0;
small=gcd(A,B);
divisor=A/small;
divisor*=B/small;
divisor*=small;
String answer=String.valueOf(divisor);
bw.write(answer+"\n");
}
br.close();
bw.flush();
bw.close();
}
public static int gcd(int a,int b){
if(a%b==0){
return b;
}
return gcd(b,a%b);
}
}
결국 다시 유클리드 호제법을 이용한 GCD
로 풀었다.
public static int gcd(int a,int b){
if(a%b==0){
return b;
}
return gcd(b,a%b);
}
시간초과.. 이제 뭐만하면 시간초과다..