返回小组 开始 2026-10-05 08:40:00

2026CSP-J/S(10.5)模拟练习

结束 2026-10-05 17:20:00
Contest is over.
当前 2026-10-11 11:58:27

G. 数字工程

描述

ACM 实验室开启了一个数字工程项目,希望把正整数 n 通过一些特殊方法变成 1。

可采用的方法有:

  1. 减去 1
  2. 除以它的任意一个素因子。

每操作一次消耗一个单位的能量。

请问把 n 变成 1 最少需要消耗多少能量?

输入

本题有多组数据。

对于每组测试,一行一个整数 n。

输出

一行一个整数,表示最少消耗的能量。

样例

输入

1
4

输出

0
2

提示

1 \le n \le 10^6。


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交