[ python level 1 ] 약수의 합

📌 약수의 합

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하자.

💡 나의 풀이

약수를 구하는것엔 3가지 방법이 있다.
1. 처음부터 n까지 약수 구하기
2. 처음부터 n//2까지 약수 구하기
3. 처음부터 int(n**0.5)까지 약수 구하기

이전에 소수 판별 문제를 풀었을 때 범위를 제곱근까지만 구해서 소수를 구했었는데, 이번에는 2로 나눈값으로 구했다.

약수의 주요 특징은 자신을 제외한 가장 큰 약수는 n//2다.
예를 들어 n = 12일때는 자신을 제외한 가장 큰 약수는 6이고(1, 2, 3, 4, 6, 12) n = 30일때는 자신을 제외한 가장 큰 약수는 15다.(1, 2, 3, 5, 6, 10, 15, 30)

이처럼 범위를 n // 2+1까지만 구해주고 자기 자신을 더해주면 문제에서 요구하는 n의 약수를 모두 더한 값이 된다.

물론, 몫을 2로 나누지 않아도 정답판정이 나오지만 수가 커질수록 계산해야하는 수가 많아지게 된다.

제곱근으로 구할때는 다음의 성질을 이용한다.
n = 12일때, 제곱근(int(n**0.5)) == 3까지 구한 약수 1, 2, 3을 이용해 n//1 = 12, n//2 = 6, n//3 = 4를 통해 약수를 구하면된다. 이때, 제곱수는 한번만 약수에 포함되야하므로 if n != n//i:를 붙여주었다.

만약 n = 1,000,000라면, 1000번의 반복만으로 결과를 출력할 수 있으므로 시간복잡도가 현저하게 줄어듦을 확인 할 수 있다.

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

# 2번
def solution(n):
    return n + sum([i for i in range(1, (n//2)+1) if n % i == 0])

# 3번
def solution(n):
    result = 0

    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            result += i
            if n != n//i: # 제곱 수는 한번만 넣기
                result += (n//i) 
    return result