시간복잡도를 줄이는 약수의 합 구하는 알고리즘(Python)

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

제한 사항
n은 0 이상 3000이하인 정수입니다.

처음 풀었던 방식은 시간복잡도를 O(N)으로 코드를 작성해보았다.

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

그러다 문득 규칙을 발견했다.
12라는 정수의 약수는 1, 2, 3, 4, 6, 12 이다. 자기 자신이 약수라는 것을 제외했을 때 가장 큰 약수는 12/2를 한 값이다. 이러한 규칙을 발견한 후 이런 코드를 짤 수 있게 되었다.

1부터 6까지 for문으로 자기자신을 제외한 약수의 값들을 다 더한 후 자기자신을 더하면 약수의 합을 구할 수 있는 로직을 짰다.
이렇게 되면 시간복잡도는 O(1/2N)으로 첫 번째 코드보다 간결해진다.

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

여기서 더 시간복잡도를 간단히 만들 수 있나 고민해보았다.
12라는 정수의 약수는 1, 2, 3, 4, 6, 12 이다. 이것을 좀 더 가독성 있게 나열해보자면,

1*12 = 12
2*6 = 12
3*4 = 12

12의 제곱근만큼 for문을 돌린다면 나머지 약수의 값도 구할 수 있다.
즉, 12의 제곱근은 3.xxx가 될테므로 for문을 3까지만 돌리면 1의 반대쪽 값인 12, 2의 반대쪽 값인 6, 3의 반대쪽 값인 4까지 구할 수 있다.

그런데 여기서 생각해보아야 할 게 있다. 이런 경우라면 어떨까?

[9의 약수]
1*9 = 9
3*3 = 9

이렇게 딱 떨어지는 제곱근(4, 9, 16, 25...)의 경우 중복 값이 있어서 중복된 값이 더해질 수 있다.

이러한 로직을 고려하여 코드로 구현해보자면,

import math

def solution(n):
    sum = 0
    for i in range(1, int(math.sqrt(n))+1):
        if(n % i == 0):
            if(i*i == n):
                sum += i
            else:
                sum += i
                sum += n//i
    
    return sum

가장 효율적인 방법은 제곱근을 이용하여 시간복잡도를 O(제곱근 N)이라 할 수 있겠다.