15897 파이썬 백준

문제)

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

15897번: 잘못 구현한 에라토스테네스의 체

 

소스코드)

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

이것을 참고하자.