백준 17427 약수의 합2

17427번: 약수의 합 2

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더

www.acmicpc.net

약수를 구하는 방법은 총 2가지로 알고 있었다.

1. 자연수 N이 주어졌을 때, 1부터 N까지 나누어가면서 나머지가 0인 값을 구하는 방법 => $O (n^{2})$

2. 자연수 N이 주어졌을 때, 약수는 서로 대칭구조를 이루고 있으므로 1부터 $\sqrt{A}$ 까지의 약수를 구하는 방법 => O(n√(n))

시간제한이 0.5초 이기 때문에 위의 두 방법은 이용할 수 가 없었다.

만약 n이 7일경우

f(1) = 1

f(2) = 1 + 2

f(3) = 1 + 3

f(4) = 1 + 2 + 4

f(5) = 1+ 5

f(6) = 1 + 2 + 3 + 6

f(7) = 1 + 7

'N이하의 자연수 중에서 i를 약수로 갖는 개수는 개' 를 이용한다

import sys
input=sys.stdin.readline

n = int(input())

sum_ = 0
for i in range(1, n+1):
    sum_ += (n//i)*i

print(sum_)

티스토리툴바