Link: Lv1. 약수의 합
- 문제 설명
자연수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.
제한 사항
n은 0 이상 3000이하인 자연수입니다.
- 문제 풀이
간단한 문제지만 중요한 기본 개념 이므로 한 번 정리해 둔다.
위키피디아의 약수 뜻에 따르면, 약수(約數, 영어: divisor) 또는 인수(因數, 영어: factor)는
어떤 정수를 나머지 없이 나눌 수 있는 정수를 원래의 정수에 대하여 이르는 말이다.
이 약수를 구하는 방법은 1부터 √n 까지 나누어 떨어지는 수를 하면 된다.
√n 까지만 진행하는 이유는 n = a * b 로 생각해 보면 된다.
n = 16 일 경우를 한번 생각해 보자.
| a | 1 | 2 | 4 | 8 | 16 |
| b | 16 | 8 | 4 | 2 | 1 |
표와 같이 a = 4 를 넘어 서는 순간 나머지는 반복하게 된다.
여기서 4는 n = 16이므로 √n에 해당되는 수이다.
즉, 1부터 √n 까지 나누어 떨어졌을 때의 수와 나눈 몫이 16의 약수가 되는 것이다.
이 문제는 이 약수들을 모두 더하면 끝난다.
Source Code: sum_of_divisor.cpp