[JAVA] 최대공약수(GCD) / 최소공배수(LCM) 구하는 방법
in Blog / Algorithm / Base on Algorithm, Gcd, Lcm
안녕하세요, 해을입니다🦖
이번 글에서는 최대공약수(GCD)와 최소공배수(LCM)를 구하는 방법에 대해 알아보겠습니다!
- 💡 유클리드 호제법
- 💡 최대공약수(GCD: Greatest Common Divisor)
- 💡 최소공배수(LCM: Least Common Multiple)
- 💡 N수의 최대공약수, 최소공배수 구하기
💡 유클리드 호제법
🥨 호제법이란?
두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘
🥨 유클리드 호제법이란?
두 수의 최대공약수를 구하는 알고리즘
a,b(a>b)에 대해서 a를 b로 나눈 나머지를 r이라 하면 a,b의 최대 공약수는 b와 r의 최대공약수와 같습니다.
이에 따라 큰 수를 작은 수로 나눈 나머지로 작은 수를 다시 나누는 과정을 0이 될때까지 반복하면 최대공약수를 구할 수 있습니다.
💡 최대공약수(GCD: Greatest Common Divisor)
두 수의 공통된 약수 중에서 가장 큰 수
유클리드 호제법을 이용하여 구함
🥨 재귀 방식으로 구현
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
🥨 반복문으로 구현
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
💡 최소공배수(LCM: Least Common Multiple)
두 수의 공통된 배수 중에서 가장 작은 수
두 수의 곱에 최대 공약수를 나눈 값과 같음
🥨 최대공약수를 이용하여 구현
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
💡 N수의 최대공약수, 최소공배수 구하기
배열을 순회하면서 배열에 있는 모든 수의 최대공약수/최소공배수를 구합니다.
🥨 최대공약수
public static int gcd(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = gcd(result, arr[i]);
}
return result;
}
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
🥨 최소공배수
public static int lcm(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = lcm(result, arr[i]);
}
return result;
}
public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
.
오류 및 오타 등 피드백, 질문, 인사 등 무엇이든 언제나 환영입니다!
읽어주셔서 감사합니다.
끝!🦕
.
👍 참고
