내 잡다한 노트
15897 파이썬 백준 본문
문제)
https://www.acmicpc.net/problem/15897
15897번: 잘못 구현한 에라토스테네스의 체
성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너
www.acmicpc.net
소스코드)
n = int(input())
arr = []
ans = n
j = 0
i = 2
while n > i:
j = (n - 1) // ((n - 1) // i)
num = 1 + (n - 1) // i
ans += (j - i + 1) * num
#print(i, j, num, ans)
i = j+1
if n != 1:
ans += 1
print(ans)
왤캐 어렵지... 플레 문제를 많이 풀진 않았으나 플레급 같은 문제 ㅋㅋㅋ;;
자력으로 풀지 못해 다른 사람의 풀이를 검색했으나 도통 이해가 되지 않았다.
시간복잡도를 루트로 푸는 방법이 있는데 진짜 이해를 하지 못하겠다.
마지막으로 찾아본 사이트에서 참고해 문제를 풀었다.
harmonic lemma를 이용해 푼다고 한다.
https://ahgus89.github.io/algorithm/Harmonic-Lemma/
Harmonic-Lemma
약수를 세는 것 보다 배수를 세는 게 쉽다.
ahgus89.github.io
이것을 참고하자.
'백준, 프로그래머스(파이썬)' 카테고리의 다른 글
| 2225 합분해 파이썬 백준 (0) | 2022.07.02 |
|---|---|
| 15683 백준 파이썬 구현+브루트포스+BFS (0) | 2022.05.21 |
| 1612 파이썬 백준 가지고 노는1 (0) | 2022.05.18 |
| 11725 파이썬 백준 트리 (0) | 2022.05.08 |
| 2250 파이썬 백준 (0) | 2022.05.08 |