주어진 숫자의 짝수 약수(even factor)의 합을 구하는 것은 코딩 테스트나 수학적 문제 해결에서 자주 등장하는 주제입니다. 이 글에서는 Java를 활용해 이를 효율적으로 계산하는 방법을 예제 코드와 함께 자세히 살펴보겠습니다.
예제 코드
import java.util.*;
import java.lang.*;
public class Demo{
public static int factor_sum(int num){
if (num % 2 != 0)
return 0;
int result = 1;
for (int i = 2; i <= Math.sqrt(num); i++){
int count = 0, current_sum = 1;
int current_term = 1;
while (num % i == 0){
count++;
num = num / i;
if (i == 2 && count == 1)
current_sum = 0;
current_term *= i;
current_sum += current_term;
}
result *= current_sum;
}
if (num >= 2)
result *= (1 + num);
return result;
}
public static void main(String argc[]){
int num = 36;
System.out.println("The sum of even factors of the number is ");
System.out.println(factor_sum(num));
}
}
실행 결과
The sum of even factors of the number is 78
숫자 36의 짝수 약수는 2, 4, 6, 12, 18, 36이며, 이들의 합인 78이 정상적으로 출력되는 것을 확인할 수 있습니다.
코드 설명
Demo라는 클래스 안에는 factor_sum이라는 함수가 정의되어 있습니다. 이 함수는 입력받은 숫자의 약수를 분석하여 짝수 약수만 골라 합산한 뒤, 그 결과값을 반환하는 역할을 담당합니다.
main 함수에서는 짝수 약수의 합을 구하고자 하는 숫자(예제에서는 36)를 정의하고, 이 값을 인자로 전달하며 factor_sum 함수를 호출합니다. 함수가 반환한 최종 결과는 안내 메시지와 함께 콘솔에 출력됩니다.
알고리즘의 동작 원리
이 코드는 단순 반복문으로 모든 약수를 하나씩 확인하는 대신, 소인수분해를 활용해 계산 속도를 크게 높입니다. 동작 과정은 다음과 같습니다.
- 입력값이 홀수라면 짝수 약수가 존재하지 않으므로 즉시 0을 반환합니다.
- 짝수라면 2부터 숫자의 제곱근까지 반복하며 소인수분해를 진행합니다.
- 소인수 2에 대해서는 2⁰(즉 1)을 제외한 거듭제곱의 합(2, 4, 8...)을 구합니다. 이를 통해 홀수 성분이 자동으로 제외됩니다.
- 나머지 소인수들에 대해서는 일반적인 약수의 합 공식(1 + p + p² + ...)을 적용합니다.
- 각 소인수별 합을 모두 곱하면 전체 짝수 약수의 합이 완성됩니다.
예를 들어 36은 2² × 3²로 분해되며, 2의 거듭제곱 합(2 + 4 = 6)과 3의 거듭제곱 합(1 + 3 + 9 = 13)을 곱하면 6 × 13 = 78이 됩니다. 이는 실제 짝수 약수들을 직접 더한 값과 정확히 일치합니다.