BOJ#2609 최대공약수 최소공배수

BOJ#2609 최대공약수 최소공배수

* 문제

https://www.acmicpc.net/problem/2609

* 풀이

두 자연수 a, b가 주어졌을 때 (a>b),

두 자연수의 최대공약수를 구하는 알고리즘 : 유클리드 호제법

두 자연수의 최소공배수를 구하는 알고리즘 : a*b/최대공약수

유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.

호제법이란, 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다.

m >= n일 때,

① m을 n으로 나눈다. 나머지를 r이라고 한다.

② 나머지 r이 0이면 n이 최대공약수이다. 나머지가 0이 아니라면 m의 값을 n으로 설정하고, n의 값은 r로 설정한 다음 ①로 되돌아가서 반복한다.

출처 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

a = Integer.parseInt(st.nextToken()); b = Integer.parseInt(st.nextToken()); multiple = a * b; // swap if (a < b) { a = a ^ b; b = a ^ b; a = a ^ b; } // GCD, Greatest Common Divisor // Euclidean algorithm while (b > 0) { mod = a % b; a = b; b = mod; } GCD = a; // LCM, Least Common multiple LCM = multiple / GCD; System.out.println(GCD); System.out.println(LCM);

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%232609_GCD_LCM