[DAY-32] 백준 17427 약수의 합2

1. 문제 

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

 

---

 

2. 문제 풀이 

import sys

N = int(sys.stdin.readline())

answer = 0

def divisor(num):
    sum = 0
    for i in range(1, int(num**(1/2)) + 1):
        if num % i == 0:
            sum+=i
            if (i**2) != num: 
                sum+=(num//i)

    return sum

for num in range(1, N+1):
    answer+= divisor(num)
    print(answer)
    

print(answer)

 

시간 초과였다...ㅎ

아무리 줄여도 2중 반복문이니까 O(N^2) 아닌가..? 했는데 gpt 피셜 O(N^3/2)였다. 

 

---

다른 사람들의 풀이를 참조해보았는데 

 

1의 경우 10번 등장하고 ((10/ 1) * 1)

2의 경우 5번 등장하고 ((10/2) * 2) 

3의 경우 3번 등장하게 되므로 ((10/3) *3)

 

이를 통해서 

 

(N / i) * i 식을 얻을 수 있다. 

 

import sys

N = int(sys.stdin.readline())

answer = 0

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

 

이거 이 방법 말고 다르게 푸는 방법이 있긴 한가? 

 

 

참고: https://liltdevs.tistory.com/49

백준 boj 17427 - 약수의 합 2 (파이썬, python)