728x90
문제
두 자연수 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)를 출력한다.
코드
import sys
n = int(sys.stdin.readline())
answer = 0
for i in range(1,n+1):
answer += (n//i) *i
print(answer)
풀이
바로 생각해내기 어려웠다.
2의 배수를 생각해보자.
2, 4, 6, 8, ... 당연히 2의 배수니까 모든 배수에 2가 포함되어 있다.
n이 4라면 4//2 = 2 -> 2가 2번 있다.
n이 8라면 8//2 = 4 -> 2가 4번 있다.
....
i 가 n // i 번 있다는 것이다.
그래서 아래와 같이 코드를 작성했다.
answer += (n//i) *i
출처 : 백준
'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
[백준] 15685 드래곤 커브 python (0) | 2022.05.23 |
---|---|
[백준] 1316 그룹 단어 체커 python (0) | 2022.03.29 |
[백준] 10972 다음 수열 python (0) | 2022.03.27 |
[백준] 1476 날짜 계산 python (0) | 2022.03.26 |
[백준] 3085 사탕 게임 python( *) (0) | 2022.03.26 |