[코테] 백준 수학 17427번 문제

17427번 : 약수의 합 2

문제 링크

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

문제 설명

두 자연수 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)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

문제풀이

이 문제의 핵심은 어떤 수 N의 약수를 구하는 것이 아닌 1부터 문제에서의 최대값인 1000000까지의 수를 순회하며 해당 수의 배수의 합을 미리 구하고 결과를 출력하는 데 있다.

import sys
input = sys.stdin.readline

MAX = 1000001
dp = [0] * MAX

for i in range(1, MAX):
    for j in range(i, MAX, i) :
        dp[j] += i

prefix_sum = [0] 
for num in dp[1:]:
    prefix_sum.append(prefix_sum[-1] + num)

print(prefix_sum[int(input())])