최대공약수를 구하기 위해 유클리드 호제법을 사용했고
최소공배수를 사용하기 위해 구한 최소공배수 값을 활용했다.
cf) 유클리드 호제법 :
GCD(a, b) = GCD(b, r)이다.
이 때, r = a를 b로 나눈 나머지이다.
r = 0이 될때, b가 최대공약수가 된다.
ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) -> 최대공약수 = 8
cf) 최소공배수 = gcd*(a/gcd)*(b/gcd)이다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num1 = sc.nextInt();
int num2 = sc.nextInt();
int GCD = gcd(num1, num2);
System.out.println(GCD);
System.out.println(lcm(GCD, num1, num2));
}
public static int gcd(int a, int b) { // 유클리드 호제법 사용
while (b != 0) {
int r = a%b;
a = b;
b = r;
}
return a;
}
public static int lcm(int gcd, int a, int b) {
return gcd*(a/gcd)*(b/gcd); // 최소공배수 LCM = gcd*(a/gcd)*(b/gcd)이다.
}
}
'알고리즘 > 백준 알고리즘(JAVA)' 카테고리의 다른 글
JAVA)1929번 M이상 N이하의 소수구하기 - 에라토스테네스의 체 (0) | 2020.07.19 |
---|---|
JAVA)1978번 소수 판별 문제 (0) | 2020.07.19 |
JAVA)17299번 오등큰수 구하기 - Stack(스택) 사용 (0) | 2020.07.18 |
JAVA)17298번 오큰수 구하기 - Stack(스택) 사용 (0) | 2020.07.17 |
JAVA)10799번 쇠막대기 자르기 - 스택(Stack) 사용 (0) | 2020.07.16 |
알고리즘/백준 알고리즘(JAVA) 카테고리의 다른 글
JAVA)1929번 M이상 N이하의 소수구하기 - 에라토스테네스의 체
JAVA)1978번 소수 판별 문제
JAVA)17299번 오등큰수 구하기 - Stack(스택) 사용
JAVA)17298번 오큰수 구하기 - Stack(스택) 사용