💡 이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될때까지 작동하여 최대공약수를 구하는 방식입니다.
1. 재귀 방식으로 구현
💡 b가 0이라면 a가 최대공약수가 되며, 그렇지 않으면 b와 a % b의 최대공약수를 구합니다. 💡 이를 재귀적으로 반복하여 최대공약수를 구할 수 있습니다.
// 재귀 방식
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
2. 반복문 방식으로 구현
💡 먼저, 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) 구현
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
2) N수의 최대공약수, 최소공배수 구현방법
1. 최대공약수(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) 구현
💡 해당 부분에서는 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);
}
