[Python] 프로그래머스 문풀 :: 정수n의 약수 합 구하기

출처: [프로그래머스 스쿨 - 코딩테스트 연습 - Python3_level1] 

링크: https://school.programmers.co.kr/learn/courses/30/lessons/12928

---

문제: 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성

1. 빈 리스트에 append

빈 리스트에 약수에 해당하는 값을 append한 후 sum

def solution(n):
    answer_list = []
    for num in list(range(1, n+1)):
        if n%num == 0:
            answer_list.append(num)
    answer = sum(answer_list)
    return answer

2. List Comprehension사용 

for문에 if조건을 사용하는 list comprehension으로 약수의 합을 구함

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

3. num / 2 를 사용

<- , rhdudals0659 , - , ->님의 풀이

약수는 숫자의 절반 이상의 값이 발생하지 않는 다는 것을 활용

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

4. 제곱근을 활용

약수는 대칭적인 성질을 활용.
어떤 수 n의 약수 a가 있다면 반드시 n/a도 n의 약수가 된다. 

from math import sqrt

def solution_final(num):
    divisor_sum = 1  # 1은 모든 자연수의 약수이므로 미리 더하기(if문을 1회 덜 돌림)
    sqrt_num = int(sqrt(num))  # 제곱근을 구하기

    for i in range(2, sqrt_num + 1):
        if num % i == 0:
            divisor_sum += i
            if i != num // i:  # 중복을 피하기 위해 != 조건 추가
                divisor_sum += num // i
    return divisor_sum

4. 최종정리

4번 방법이 가장 효율적이라고 생각됨
ex) num = 100일 때
1,2번 = 100회, 3번 = 50회(100/2) 4번 = 10회(100*0.5)