1 min to read
유클리드 호제법(GCD, LCM)
유클리드 호제법(GCD, LCM)을 배워봅시다.

최대공약수GCD, Greatest Common Divisor
최소공배수 LCM, Least Common multiple
위 사진을 보시면 쉽게 이해하실 수 있을거예요!
이해가 되셨다면 코드로 바꿔볼까요?
int a, b;
int multiple;
int mod = 0;
int GCD = 0, LCM = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
multiple = a * b;
// 나누는 값이 작아야겠죠? 크다면 바꿔줍시다.
if (a < b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
while (b > 0) {
mod = a % b;
a = b;
b = mod;
}
GCD = a;
LCM = multiple / GCD;
System.out.println(GCD);
System.out.println(LCM);
Comments