유클리드 호제법 (백준)
•
최대 공약수 : A와 B 두 수가 주어지면 A의 약수들을 모두 구하고, B의 약수들을 모두 구한 뒤 공통 된 약수들만 찾아내어
약수들의 곱으로 다시 나타내준다.
•
정리
두 수 a, b ∈ ℤ 이고, r = a mod b 이라고 한다. (r 은 a에 b를 나눈 나머지를 의미)
이 때 r은 (0 ≤ r < b) 이고, a ≥ b 이다.
이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.
즉, GCD(a, b) = GCD(b, r)
•
최소 공배수: A와 B 두 수가 주어진다면 A,B의 공통된 최소 배수
•
정리
최대공약수를 구해준 뒤 입력받은 두 수의 곱에서 최대공약수를 나눠준다.
•
코드
import java.util.Scanner;
public class N2609 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long num1 = sc.nextLong();
long num2 = sc.nextLong();
long gcd =getGCD(Math.max(num1, num2), Math.min(num1, num2));
long lcm =getLCM(num1, num2, gcd);
System.out.println(gcd);
System.out.println(lcm);
}
public static long getGCD(long a, long b) {
while(b > 0) {
long tmp = a;
a = b;
b = tmp%b;
}
return a;
}
public static long getLCM(long a, long b, long gcd) {
return (a*b)/gcd;
}
}
Plain Text
복사