408366: GYM103107 F Function

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Functiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

One day, Little Y came cross a function that confused her a lot.

$$$$$$ f(n) = \begin{cases} 1, & n \in \{1\} \bigcup \operatorname{Prime} \\ p\,f(p^{k-2}), & n = p^k ~ (p \in \operatorname{Prime}; ~ k > 1) \\ f(p_1^{e_1})\prod_{i=2}^r {p_i}^{e_i}, & n = \prod_{i=1}^r {p_i} ^ {e_i} ~ (p_1 < p_2 < \cdots < p_r; ~ p_i \in \operatorname{Prime}; ~ r \ge 2) \end{cases} $$$$$$

Now Little Y is interested in $$$\sum_{i=1}^n f(i)$$$. Can you help her?

Input

One line contains one integer denoting $$$n ~ (1 \le n \le {10}^{7})$$$.

Output

One line, the number denoting the answer.

ExamplesInput
10
Output
20
Input
100
Output
1487
Note

For the first sample, $$$f(1) = 1$$$, $$$f(2) = 1$$$, $$$f(3) = 1$$$, $$$f(4) = 2$$$, $$$f(5) = 1$$$, $$$f(6) = 3$$$, $$$f(7) = 1$$$, $$$f(8) = 2$$$, $$$f(9) = 3$$$, $$$f(10) = 5$$$.

It is guaranteed that the answer will always be less than $$$2^{64}-1$$$.

Little Y wonders whether you can solve $$$n$$$ up to $$${10}^{10}$$$.

加入题单

上一题 下一题 算法标签: