정수 n을 입력받아 n의 약수를 모두 더한 값을 반환하는 함수 구현하기
정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.
n
은 0 이상 3000이하인 정수입니다.
n | return |
12 | 28 |
5 | 6 |
약수란, 어떤 수를 나머지 없이 나눌 수 있는 자연수이므로, i=1부터 n까지 for
문을 돌면서, 나누어 떨어지는 수를 answer
에 더해주면 된다.
function solution(n) {
var answer = 0;
for(let i = 1; i <= n; i++ ){
if(n % i === 0) answer+=i;
}
return answer;
}
def solution(n):
answer = 0
for i in range(1, n + 1):
if n % i == 0:
answer += i
return answer
n
의 값으로 아주 큰 값이 들어오게 된다면, 반복문의 횟수가 많아지는 문제가 있다.
n
의 제곱근까지만 반복을 수행해서 이를 개선할 수 있다.
제곱근까지만 반복을 수행해도 실제 약수를 모두 구할 수 있기 때문이다!
위 내용을 반영하면, 아래와 같이 함수를 변경할 수 있다.
function solution(n) {
let answer = 0;
for (let i = 1; i * i <= n; i++) {
if (n % i === 0) {
answer += i;
if (i !== n / i) {
answer += n / i;
}
}
}
return answer;
}
def solution(n):
answer = 0
i = 1
while i * i <= n:
if n % i == 0:
answer += i
if i != n // i:
answer += n // i
i += 1
return answer