P9238 [蓝桥杯 2023 省 A] 翻转硬币
题目描述
给定 $n$ 个按顺序摆好的硬币，一开始只有第 $1$ 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 $i$ 并将所有满足 $j \bmod i=0$ 的位置 $j$ 的硬币翻转。
求最少需要多少次操作可以让所有硬币都朝上。
输入格式
无
输出格式
无
说明/提示
#### 【评测用例规模与约定】
对于 $30 \%$ 的评测用例，$n \leq 5 \times 10^6$；
对于 $70 \%$ 的评测用例，$n \leq 10^9$；
对于所有评测用例，$1 \leq n \leq 10^{18}$。