[백준-골드5] 17425번 약수의 합 (수학, PyPy3)

https://www.acmicpc.net/problem/17425

17425번: 약수의 합

 

<내 코드>

- dp 리스트에 각 수에 해당하는 약수의 합을 계산해서 넣는다. 

  -> 에라토스테네스의 채 같은 느낌

  -> 모든 수는 1을 약수로 가지기 때문에 dp 리스트는 1로 초기화한다.

- s 리스트는 약수의 누적합을 담는 리스트이다. 

  -> for문을 돌면서 s리스트의 인덱스 -1 + dp리스트를 해서 누적합을 계산한다.

 

import sys
input = sys.stdin.readline

Max = 1000001

dp = [1]* Max #각 수 별로 1-Max 까지 약수의 합 
s = [0] * Max #누적값

for i in range(2, Max):
    j = 1
    while i*j < Max:
        dp[i*j] +=i
        j += 1
        
for i in range(1, Max):
    s[i] = s[i-1] + dp[i]
    
t = int(input())
for _ in range(t):
    n = int(input())
    print(s[n])