[알고리즘] 백준 17425 파이썬 - 약수의 합

 

 

17425번: 약수의 합

문제

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

 

 

 

문제풀이

import sys
input = sys.stdin.readline
#01
max=1000000
dp=[0]*(max+1)
s=[0]*(max+1)
#02
for i in range(1,max+1):
    j=1
    while i*j<= max:
        dp[i*j]+=i
        j+=1
#03
for i in range(1,max+1):
    s[i] = s[i-1]+dp[i]
#04
n = int(input())
ans=[]
for _ in range(n):
    a = int(input().rstrip())
    ans.append(s[a])
print("\n".join(map(str,ans))+'\n')

- #01 : 문제에서 주어진 최대의 값을 설정해주고, dp와 s는

           각각 각 숫자의 약수와 약수의 누적합을 말한다.

- #02 : while문에서 i*j 값이 max 범위 안이라면 dp[i*j] 값에 i를 더해준다.

           그 이유는 i의 배수는 무조건 그 값의 약수가 되기에,

           i*j의 값에 i를 미리 더하는 것이다. j는 점차 늘려서 max 전까지 진행한 후 

           다음 i값으로 넘어가 같은 과정을 반복한다.

- #03 : i번째의 수까지 약수의 누적 합을 s에 저장한다. 

- #04 : n과 a를 입력받아 해당하는 s의 누적값을 출력해준다.