[백준] Code.Plus 수학 - 17425.약수의 합

약수의 합

문제

두 자연수 A와 B가 있을 때, A = BC를  만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 ㅑ약수는 1, 2가 있고, 1, 2, 3, 4, 6, 8 ,12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다.
x보다 작거나 같은 모든 자연수 y의 f(y)값ㅇㄹ 더한 값은 g(x)로 표현한다

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)을 출력한다

코드

import sys

# 최대값 설정
MAX = 1000000

# 각 인덱스마다 약수의 합을 담아 놓을 배열 초기화
dp = [0] * (MAX + 1)
# 각 인덱스까지 누적합을 담을 배열 초기화
s = [0] * (MAX + 1)

for i in range(1, MAX + 1): #1부터 최대값까지
    j = 1 # i에 곱할 j를 선언
    while i * j <= MAX: # i * j 값이 최대값이 넘지 않을 때까지
        # dp배열의 인덱스인 i의 배수에 i 값을 더해준다. 
        dp[i * j] += i #예를들면 3*j의 해당하는 값들은 3을 무조건 약수로 가지기 때문에 3을 더해준다 
        j += 1 #j값 증가
    s[i] = s[i - 1] + dp[i] #해당 dp[i]의 값 까지 더한 누적합을 s배열에 넣어준다.

t = int(input()) #테스트 케이스 개수 입력

for _ in range(t):
    a = int(sys.stdin.readline())
    sys.stdout.write(str(s[a])+"\n")