[파이썬] 백준 17425 번 : 약수의 합

출처 : www.acmicpc.net/problem/17425

17425번: 약수의 합

이 문제는 dabonee.tistory.com/19

[파이썬] 백준 17427 번 : 약수의 합2

위 문제와 같지만 다른 문제이다. 약수의 합2와 같은 방법으로 푼다면 시간초과가 나기 때문에 다른 방법을 찾아야 한다.

여기서 d라는 배열에 약수의 합을 구하였다. 이 때, 배수의 원리를 이용하였다.

예를 들어 6이라는 숫자를 들어보자. 1부터 6까지 1의 배수는 모두 다 해당되고 2의 배수는 2,4,6이 해당된다. 이렇게 해당되는 곳에 표시를 하면 아래와 같다. 

 

d	1	2	3	4	5	6
1	1	1	1	1	1	1
2		2		2		2
3			3			3
4				4
5					5
6						6

우리는 위에 표에서 해당하는 열의 값을 더하여 약수의 합을 구할 수 있다. 

또한 s라는 배열에 1부터 n까지 약수의 합을 모두 더하여 넣어주었다.

MAX = 1000000;
d = [1]*(MAX+1)
s = [0]*(MAX+1)
for i in range(2, MAX+1):
    j = 1
    while i*j <= MAX:
        d[i*j] += i
        j += 1
for i in range(1, MAX+1):
    s[i] = s[i-1] + d[i]
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    ans.append(s[n])
print('\n'.join(map(str,ans))+'\n')