E - Sum of f(n) /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点: 100

Xmas Contest 2013 問題 G を見たくろうさを遠くから見たしろうさ「ふむふむ,f(n) の和が高速に計算できるのか」

問題文

正の整数 n に対し,f(n)n が持つ素因数を重複を込めて数えた個数とする.例えば,200 = 2^3 \times 5^2 なので,f(200) = 5 となる.

正の整数 N が与えられるので,\sum_{n=1}^N f(n) を求めよ.

制約

  • 1 \le N \le 10^{11}

部分点

  • N \le 10^{10} を満たすデータセットに正解した場合は,45 点が与えられる.
  • 追加制約のないデータセットに正解した場合は,上記とは別に 55 点が与えられる.

入力

N

出力

\sum_{n=1}^N f(n) の値を 1 行に出力せよ.


入力例 1

6

出力例 1

7

f(1) = 0f(2) = 1f(3) = 1f(4) = 2f(5) = 1f(6) = 2 なので,答えは 0 + 1 + 1 + 2 + 1 + 2 = 7 である.


入力例 2

2019

出力例 2

6028

入力例 3

906150257

出力例 3

3660251364