백준 17427번. 약수의 합 2 (Python / 파이썬)

문제

두 자연수 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보다 작은 수들의 약수의 합을 

단순히 모두 구할 수 있겠지만

조금 더 효율적으로 코드를 작성하기 위해 생각해보면

어떤 수의 배수들은 항상 그 수를 포함하고 있습니다.

예를 들어, 

3의 배수 3, 6, 9, 12, 15, 18은 약수로 3을 포함합니다.

4의 배수 4, 8, 12, 16, 20, 24는 약수로 4를 포함합니다.

이러한 아이디어를 이용해 문제를 해결할 수 있습니다.

 

만약 주어진 자연수 N이 10이라면 

1부터 10까지 수 중 

10 // 1 (1을 약수로 갖는 수의 개수) * 1

10 // 2 (2를 약수로 갖는 수의 개수) * 2

10 // 3 (3을 약수로 갖는 수의 개수) * 3

이러한 과정을 10을 약수로 갖는 수까지 반복하면

10보다 작은 모든 자연수들의 약수의 합을 구할 수 있습니다.

 

따라서, 주어진 수식을 코드로 구현해 

구하고자 하는 값을 출력해주었습니다.

---

My Code

n = int(input()) # 자연수 n

sum_value = 0
for i in range(1, n + 1): 
    # 약수 i를 갖는 수의 개수 * i를 구해 더해줌
    sum_value += (n // i) * i 

print(sum_value)