1934번: 최소공배수
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있
www.acmicpc.net
단순하게 최소 공배수를 구하는 문제이다.
이 문제에서 포인트는 최소 공배수는 A와 B 가 주어졌을 때 "A*B / 최대공약수" 를 계산해 구할 수 있다. 는 것이다.
결국 유클리드 호제법을 이용해서 최대 공약수를 구하면 해결 할 수 있다.
유클리드 호제법에 관해 정리해 둔 글이다.
[JAVA] 유클리드 호제법 - 최대 공약수 구하기
최대 공약수를 구하는 방법 일반적으로 최대 공약수를 구하려고 하면 소인수 분해를 이용해서 공통된 소수들의 곱으로 표현한다. 그러나 소인수 분해를 위해 소수를 먼저 찾아야 하고, 찾은 소
hyeondaya.tistory.com
코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class p1934 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
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 result = A * B / gcd(A, B);
System.out.println(result);
}
}
private static int gcd(int A, int B ){
if(B==0) return A;
else return gcd(B, A % B);
}
}