[프로그래머스] 약수의 합

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

 

약수 문제를 어디선가 풀었던 것 같은데 기억이 안난다.

여튼 내가 푼 방식은 n만큼의 반복문을 돌며 나누었을 때 나머지가 0인 것을 찾아 sum에 더해준다. 

def sumDivisor(num):
    # num / 2 의 수들만 검사하면 성능 약 2배 향상잼
    return num + sum([i for i in range(1, (num // 2) + 1) if num % i == 0])

 

그리고 다른 분의 아주 간단한 코드를 보았는데, 댓글들을 보니 다들 감탄하고있다.

여기서 num // 2 + 1을 해준 값만 확인하는 이유가 무엇인지 고민해보았다.

 

예를 들어 num이 12라고 해보자.

12의 약수는 1, 2, 3, 4, 6, 12인 점을 기억하고 코드를 하나하나 뜯어보면

 

일단 반복문에서 num // 2의 값까지만 보면 6까지 보게 된다. 그렇다면 맨 마지막 약수인 12를 보지 못하게 되기에 앞에서 num을 더해주는 것이라고 볼 수 있다.

 

그렇다면 num이 21일 때는 약수가 1, 3, 7, 21이며, 21 // 2의 값은 10까지이다. 또 마지막 약수이자 자기 자신인 21을 더해주지 못하기에 num에게 더해주는 것을 확인할 수 있다.

 

도대체 이런 생각은 어떻게 하는거지!??!?!