<aside> ✅ 개념
[Java/Short] 최대공약수, 최소공배수 구하는 방법 : 두 수 또는 N개의 수
CF. 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미합니다.
[Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609)
소인수분해를 통해 코드로 구현한다면?
우선 소인수분해를 위해 소수를 먼저 찾아야 하고, 찾은 소수가 두 개의 수를 공통적으로 나눌 수 있는지를 확인을 해야 하기 때문에 비효율적
→ 만약 주어진 두 개의 수가 매우 크다면 시간 복잡도는 계속 증가
유클리드 호제법
두 개의 수 A, B가 존재하고, A를 B로 나눈 나머지를 C라고 하겠습니다. (A > B)
이때, A와 B의 최대공약수는 B와 C의 최대공약수와 같습니다. EX. A = 21, B = 14, C = 7 → 최대공약수 7
이러한 성질을 이용해서 계속적으로 나눗셈을 진행해서 C가 0이 되었을 때, 즉 나머지가 0이 되었을 때의 나누는 수가 최대공약수가 됩니다.
진짜 A와 B의 최대공약수는 B와 C의 최대공약수와 같을까?
[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]
public class BOJ_2609 {
// 백준온라인저지 2609번 최대공약수와 최소공배수 Java로 문제풀이
public static void main(String[] args) {
// 주어진 입력정보 받기
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
// 유클리드 호제법을 사용해서 두수의 최대공약수 얻기
int N = gcd(Math.max(A, B), Math.min(A, B));
// 최대공약수로 두수를 나눠서 몫 구하기
A = A / N;
B = B / N;
// 두 수의 최소공배수 = 두 수의 최대 공약수 * 위에서 구한 몫
int M = A * B * N;
// 출력
System.out.println(N);
System.out.println(M);
}
/**
* 유클리드 호제법 구현 메서드
* @param bn : 큰 숫자
* @param sn : 작은 숫자
* @return
* 큰 숫자를 작은숫자로 나눈 값이 0이면 작은숫자 리턴, 아니면 재귀형태로 자신을 호출
*/
static int gcd(int bn, int sn) {
// 큰숫자를 작은숫자로 나눈 나머지를 계산
int r = bn % sn;
// 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
if (r == 0) {
return sn;
} else {
// 나머지가 0 이상이면 재귀형태로 호출
// 이때 파라미터는 작은숫자와 나머지를 넣어줌
return gcd(sn, r);
}
}
}