蓝桥杯2023年第十四届省赛真题-翻转硬币

给定 n 个按顺序摆好的硬币，一开始只有第 1 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 i 并将所有满足 j mod i = 0 的位置 j 的硬币翻转。

求最少需要多少次操作可以让所有硬币都朝上。

输入一行包含一个整数 n 。

输出一行包含一个整数表示最少需要的操作次数。

对于 70% 的评测用例，n ≤ 10⁹ ；

对于所有评测用例，1 ≤ n ≤ 10¹⁸。