자연수의 약수의 합 구하기
ChatGPT
자연수의 약수 합 구하기 (소인수분해 활용)
어떤 자연수 \(n\) 이 주어졌을 때, 소인수분해 결과를 이용하여 약수의 합을 구하는 방법을 정리합니다.
1. 약수의 합 공식
자연수 \(n\) 의 소인수분해가 다음과 같이 주어졌다고 가정합니다.
\[n = p_1^{e_1} \times p_2^{e_2} \times ... \times p_k^{e_k}\]이때, \(n\) 의 모든 약수의 합은 다음 공식으로 계산할 수 있습니다.
\[\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{e_i+1} - 1}{p_i - 1}\]이 공식을 이용하면, 소인수분해 결과만 알면 빠르게 약수의 합을 구할 수 있습니다.
2. 예제
예제 1: \(n = 12\)
\(12\) 를 소인수분해하면
\[12 = 2^2 \times 3^1\]공식을 적용하면,
\[\sigma(12) = \left(\frac{2^{2+1} - 1}{2 - 1}\right) \times \left(\frac{3^{1+1} - 1}{3 - 1}\right)\] \[= \left(\frac{8 - 1}{1}\right) \times \left(\frac{9 - 1}{2}\right) = 7 \times 4 = 28\]즉, \(12\) 의 모든 약수의 합은 28 입니다.
예제 2: \(n = 18\)
\(18\) 의 소인수분해는
18 = 2^1 \times 3^2 $$
공식을 적용하면,
\[\sigma(18) = \left(\frac{2^{1+1} - 1}{2 - 1}\right) \times \left(\frac{3^{2+1} - 1}{3 - 1}\right)\] \[= \left(\frac{4 - 1}{1}\right) \times \left(\frac{27 - 1}{2}\right) = 3 \times 13 = 39\]따라서 \(18\) 의 모든 약수의 합은 39 입니다.
4. 정리
- 소인수분해가 주어진 경우, 약수의 합을 빠르게 구할 수 있는 공식이 존재합니다.
- 공식:
\(\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{e_i+1} - 1}{p_i - 1}\) - 이 공식을 활용하면 \(O(k)\) (소인수 개수만큼 반복) 에 계산할 수 있어 효율적입니다.
- 생각해보니 등비수열의 합 공식끼리 곱한거네. 그게 맞긴 하지
이 방법을 활용하면 소인수분해가 주어진 상황에서 빠르게 약수의 합을 구할 수 있습니다!
5. Chat GPT가 작성한 글
이 글은 Chat GPT가 작성했다.