====== 잘못 구현한 에라토스테네스의 체 ======

===== 풀이 =====
  * 소스코드를 훑어보면 각 i에 대해서, 6번줄의 실행횟수는 1 + (n-1)/i 가 된다는 것을 확인할 수 있다.
  * 따라서 전체 실행 횟수는, m=n-1이라고 썼을때, n + ([m/1] + [m/2] + ... [m/m]) 이 된다. 
  * 이것은 [[ps:정수론적_함수#n1_n2__nn_을_계산|[N/1]+[N/2]+...+[N/N] 을 계산]]의 공식을 활용해서 O(sqrt(n))에 계산 가능하다. 자세한 것은 링크 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 15897. 잘못 구현한 에라토스테네스의 체".

- Problem link: https://www.acmicpc.net/problem/15897
- Solution link: http://www.teferi.net/ps/problems/boj/15897
"""

import math


def main():
    N = int(input())
    num = N - 1
    sqrt = math.isqrt(num)
    answer = 2 * sum(num // i for i in range(1, sqrt + 1)) - sqrt * sqrt
    print(answer + N)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}