- 먼저, b가 0이 될 때까지, a를 b로 나눈 나머지를 b에 대입하고, a와 b의 값을 교환합니다. - 이를 반복하여 최대공약수를 구할 수 있습니다.
// 반복문 방식
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
2. 최소공배수(LCM) 구현 방법
💡 최소공배수(LCM) 구현 방법 - 최대공약수의 함수를 기반으로 '최소공배수'를 구합니다.
- 해당 방식은 두 수 a와 b의 최소공배수를 구하는 함수입니다. - 함수 내부에서는 a와 b의 최대 공약수를 이용하여 최소 공배수를 계산합니다. - 최소 공배수는 두 수의 곱에 최대 공약수를 나눈 값과 같습니다.
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
3. [참고] 약수와 배수를 구하는 방법
3.1. 약수 구하기
💡약수 구하기
- for 문을 통해 1부터 n까지 반복하며 n을 i로 나누어 나머지가 0인 경우, 즉 약수일 때마다 i를 출력합니다.
int n = 12; // 약수를 구할 수
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
System.out.println(i);
}
}
3.2. 배수 구하기
int n = 3; // 배수를 구할 수
for (int i = 1; i <= 10; i++) {
System.out.println(n * i);
}
4) N수의 최대 공약수, 최소 공배수 구현하기
1. 최대 공약수(GCD) 구현
💡최대 공약수(GCD) 구현
- 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 '최대공약수'를 구합니다.
1. result 변수를 배열의 첫 번째 값으로 초기화합니다.
2. 반복문을 통해 배열의 나머지 값들과 최대공약수를 구하여 result 변수에 저장합니다.
3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최대공약수가 됩니다.
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);
}
2. 최소공배수(LCM) 구현
💡최소공배수(LCM) 구현 - 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 '최소공배수'를 구합니다.
1. result 변수를 배열의 첫 번째 값으로 초기화합니다.
2. 반복문을 통해 배열의 나머지 값들과 최소공배수를 구하여 result 변수에 저장합니다.
3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최소공배수가 됩니다.
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);
}
💡 [참고] 좀 더 다양한 알고리즘에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
