문제 설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한 사항

• n은 0 이상 3000이하인 정수입니다.

풀이

약수란, 어떤 수를 나머지 없이 나눌 수 있는 자연수이므로, i=1부터 n까지 for문을 돌면서, 나누어 떨어지는 수를 answer에 더해주면 된다.

JavaScript

function solution(n) {
    var answer = 0;
    for(let i = 1; i <= n; i++ ){
        if(n % i === 0) answer+=i; 
    }
    return answer;
}

Python

def solution(n):
    answer = 0
    for i in range(1, n + 1):
        if n % i == 0:
            answer += i
    return answer

TIL

n의 값으로 아주 큰 값이 들어오게 된다면, 반복문의 횟수가 많아지는 문제가 있다.

n의 제곱근까지만 반복을 수행해서 이를 개선할 수 있다.

제곱근까지만 반복을 수행해도 실제 약수를 모두 구할 수 있기 때문이다!

위 내용을 반영하면, 아래와 같이 함수를 변경할 수 있다.

JavaScript

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;
}

Python

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