문제

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

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

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

출력

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

풀이

에라토스 테네스의 체를 이용해서 INF까지의 숫자들의 약수들의 합을 구해줄 수 있습니다. i가 2라고 예를 든다면 (j가 1~5..)i*j => 2,4,6,8,10 .. 의 dp의 숫자들에 미리 2라는 수를 더해 놓을 수 있습니다.
그리고 문제는 N이하의 모든 약수의 합을 더하는 것이기 때문에 이런식으로 [1,3,4,7,6 -> 1,4,8,15,21 ] 차례대로 이전의 값과 지금의 합을 더해주게 됩니다. 이런식으로 dp를 이용하면 시간초과를 벗어날 수 있습니다.

import sys
sys.stdin = open('input.txt')
input= sys.stdin.readline


INF = 1000000
dp = [0]*(INF+1)
for i in range(1,INF+1): # 1부터 하나씩 모든 약수들을 적는 칸에 추가해준다.
    for j in range(1,INF//i+1):
        dp[i*j]+=i

for i in range(1,INF+1):
    dp[i] += dp[i-1]

T = int(input())

for _ in range(T):
    print(dp[int(input())])