### 问题描述 给定 $n$ 个按顺序摆好的硬币，一开始只有第 $1$ 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 $i$ 并将所有满足 $j \bmod i = 0$ 的位置 $j$ 的硬币翻转。 求最少需要多少次操作可以让所有硬币都朝上。 ### 输入格式 输入一行包含一个整数 $n$。 ### 输出格式 输出一行包含一个整数表示最少需要的操作次数。 ### 样例输入1 ``` 7 ``` ### 样例输出1 ``` 6 ``` ### 样例输入2 ``` 1131796 ``` ### 样例输出2 ``` 688042 ``` ### 评测用例规模与约定 对于 $30$% 的评测用例，$n \leq 5 \times 10^6$； 对于 $70$% 的评测用例，$n \leq 10^9$； 对于所有评测用例，$1 \leq n \leq 10^{18}$。