백준 17427번 약수의 합2

내 코드

n = int(input())

res = 0
for i in range(1, n + 1):
    for j in range(1, i + 1):
        if i % j == 0:
            res += j
print(res)

자연수 n이 주어졌을 때 g(n)을 구하려면 g(n)은 n보다 같거나 같은 자연수 x의 f(x)를 모두 더하면 된다
f(x)는 x의 약수의 합이다

i가 x일 때 j는 1 <= j <= x 값을 가지고 i의 약수를 res에 더하는 코드를 짜보았다.
2중 for문이기 때문에 시간복잡도는 O(n2)이라서 시간초과이다

풀이
자연수 N을 K로 나눴을 때 나머지가 0이면 K는 N의 약수이다. 약수는 사실 N = X * K 꼴로 표현할 수 있는데 이 표현은 N이 K의 배수라는 말과 같다.

그리고 N이하에서 K의 배수 개수는 N//K로 쉽게 구할 수 있다.

예시) N이 10
(10//1) 1 = 10 1 = (10 이하에서 1을 약수로 갖는 숫자 개수) 약수 1
(10//2) 2 = 5 2 = (10 이하에서 2를 약수로 갖는 숫자 개수) 약수 2
(10//3) 3 = 3 3 = (10 이하에서 3을 약수로 갖는 숫자 개수) * 약수 3

...

(10//9) 9 = 1 9 = (10 이하에서 9를 약수로 갖는 숫자 개수) 약수 9
(10//10) 10 = 1 10 = (10 이하에서 10을 약수로 갖는 숫자 개수) 약수 10

수식으로 정리하면

( n / i ) * i

import sys
input = sys.stdin.readline

n = int(input())

sum = 0
for i in range(1, n + 1):
	# i의 배수의 개수 = i를 약수로 갖는 수
    sum += (n // i) * i

print(sum)

시간복잡도를 줄이는 방법이 생각나지 않았다.