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

 

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

17425번: 약수의 합

---

문제 & 테스트 케이스

---

문제 해석

주어진 숫자 n까지의 약수의 합을 구하는 문제이다.

테스트 케이스처럼 2가 입력되었을때, 1의 약수는 [1], 2의 약수는 [1,  2]이다.

따라서 2까지의 수들의 모든 약수의 합은 4가 된다.

---

코드

input = __import__('sys').stdin.readline
# 약수 구하기
divisor = [0] * 1000001
divisor[1] = 1
for i in range(2, 1000001):
    for j in range(1, i + 1):
        if i * j < 1000001:
            if i == j:
                divisor[i * j] += j
            else:
                divisor[i * j] += j + i
        else:
            break

# 누적합 구하기
ans = [0] * 1000001
for i in range(1, 1000001):
    ans[i] += divisor[i] + ans[i - 1]

t = int(input())
for _ in range(t):
    n = int(input())
    print(ans[n])

---

문제 풀이

약수들의 누적합을 구하는 문제이다.

주어진 입력이 1 ~ 10000000의 수로 제한이 되어 있으므로, 먼저 해당 수의 약수를 구한 뒤

이 약수들의 누적합을 담고

입력이 주어질때마다 해당 배열에서 출력하는 방식을 생각했다.

 

먼저 약수를 어떻게 구할지 생각해보았다. 10의 약수는 10보다 작은 수부터 나누어 하나씩 확인해 나머지가 없는 수들의 집합이다.

이를 구현하려면 많은 시간이 소요될것이 뻔했다.

 

따라서 입력의 수가 제한이 있고, 소수 판별을 빠르게 할 수 있는 "에라토스테네스의 체" 알고리즘을 떠올렸다.

소수는 자신과 1을 제외한 어떠한 값으로도 나눌 수 없는 수이다. 이를 빠르게 구하기위한 방법이 에라토스테네스의 체 라는 방법이다.

이는 2부터 올라가며 현재 자신이 소수라면 자신을 제외한 자신의 배수들을 모두 제거하는 방식이다.

 

즉, 처음에 모든수가 소수임을 나타내는 배열을 생성한다.

2는 소수임을 나타내므로 2 * 2, 2 * 3 ... 범위내 수까지 반복하여 해당 수를 소수가 아님을 표현한다.

다음 수인 3 또한 위에서 걸러지지 않았으므로 3 * 2, 3 * 3 ... 을 반복하여 해당하는 수를 소수가 아님을 표현한다.

4는 2의 과정에서 걸러졌으므로 소수가 아니다.

이를 반복하여 소수 판별 테이블을 만들고, 해당 테이블을 통해 소수판별을 빠르게 할 수 있다.

 

이 방법을 약수에 적용시켰다.

반복문을 통해 2부터 범위 수 까지 반복한다.

2일때 2까지의 수를 곱해 해당하는 값에 더해준다. 즉 divisor[2 * 1]에 2와 1을 더해주고, 

divisor[2 * 2]에는 2와 2를 더해준다.

하지만 이렇게 반복한다면 divisor[4]에는 1과 2와 2와 4를 더한 값이 저장되게 된다.

따라서 자기 자신과 곱하는 경우에는 한번만 더해주도록 구현했다.

divisor = [0] * 1000001
divisor[1] = 1
for i in range(2, 1000001):
    for j in range(1, i + 1):
        if i * j < 1000001:
            if i == j: # 자기 자신과의 곱일 경우 한번만
                divisor[i * j] += j
            else:
                divisor[i * j] += j + i
        else:
            break

따라서 divisor 테이블을 만들고 이를 누적합을 통해 문제에서 요구하는 g() 값을 구하였다.