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

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

"""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()