졍's 기술 블로그

약수의 합 2

티어 : Silver 2
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 수학, 정수론

문제

두 자연수 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)를 출력한다.

예제 입출력

Algorithm

N까지의 약수 중 i라는 숫자는 N//i개 존재
-> i가 1부터 N까지 증가하면서 i의 개수 * i 더하기

Code

N = int(input())
sum_ = 0
for i in range(1, N+1):
    sum_ += i * (N//i)
print(sum_)

메모리: 30864 KB
시간: 240 ms