[BOJ] 17427번 약수의 합 2

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

17427번: 약수의 합 2

 

 

시간제한이 0.5초에 데이터의 범위는 1,000,000 이하이므로 O(n) (=약수를 하나하나 구하는것)은 시간초과가 난다.

 

1~n 의 수 중에서 1을 약수로 가지는 수는 n개, 2를 약수로 가지는 수는 n/2 개 ... 라는 것을 이용해야 한다.

 

N = int(input())

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

 

비록 간단해보이고 짧은 코드지만, 알고리즘을 생각해내는게 쉽지 않았다.