-
3-9: 최소공배수Math 2018. 10. 24. 20:04
최소공배수 (lcm.cpp)
문제
정수 B를 0보다 큰 정수인 N으로 곱해 정수 A를 구할 수 있다면 A는 B의 배수이다.
예:
- 10은 5의 배수이다 (5*2 = 10)
- 10은 10의 배수이다(10*1 = 10)
- 6은 1의 배수이다(1*6 = 6)
- 20은 1, 2, 4,5,10,20의 배수이다.
다른 예:
- 2와 5의 최소공배수는 10이고, 그 이유는 10은 2와 5 둘 다의 배수이고, 10보다 작은 공배수가 없기 때문이다.
- 10과 20의 최소공배수는 20이다.
- 5와 3의 최소공배수는 15이다.
당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.
입력
한 줄에 두 자연수 A와 B가 공백으로 분리되어 주어진다.
A와 B는 100000000(108)보다 작다.
참고: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.
출력
A와 B의 최소공배수를 한 줄에 출력한다.
예제 입력
1 1
예제 출력
1
예제 입력
3 5
예제 출력
15
예제 입력
1 123
예제 출력
123
예제 입력
121 199
예제 출력
24079
import java.util.Scanner;
public class LCM {
/**
*
* 정수 B를 0보다 큰 정수인 N으로 곱해 정수 A를 구할 수 있다면 A는 B의 배수이다.
*
* 예:
*
* 10은 5의 배수이다 (5*2 = 10)
* 10은 10의 배수이다(10*1 = 10)
* 6은 1의 배수이다(1*6 = 6)
* 20은 1, 2, 4,5,10,20의 배수이다.
* 다른 예:
*
* 2와 5의 최소공배수는 10이고, 그 이유는 10은 2와 5 둘 다의 배수이고, 10보다 작은 공배수가 없기 때문이다.
* 10과 20의 최소공배수는 20이다.
* 5와 3의 최소공배수는 15이다.
* 당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.
*
* 한 줄에 두 자연수 A와 B가 공백으로 분리되어 주어진다.
*
* A와 B는 100000000(108)보다 작다.
*
* 참고: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.
*
* 3 5
* 15
* @param args
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
// System.out.println((a*b)/gcd(a,b));
System.out.println(lcm(a,b));
}
private static long gcd(long a, long b) {
if (b==0) return a;
if (b<a) return gcd(b,a);
return gcd(a, b%a);
}
private static long lcm(long a, long b) {
long max = Math.max(a,b);
long min = Math.min(a,b);
long lcm = 0;
for (int i=1; i<=min; i++){
long x = max * i;
if (x%min ==0){
lcm= x;
break;
}
}
return lcm;
}
}'Math' 카테고리의 다른 글
3-11: 분수합 (0) 2018.10.24 3-10: 가로수 (0) 2018.10.24 3-8: 조합 0의 개수 (0) 2018.10.24 3-7: 파스칼의 삼각형과 조합 (0) 2018.10.24 3-6: 준혁이의 수열 (0) 2018.10.24