#P2618. 数字工程
数字工程
题目描述
ACM 实验室开启了一个数字工程项目,希望把正整数 通过一些特殊方法变成 。
可采用的方法有:
- 减去
- 除以它的任意一个素因子。
每操作一次消耗一个单位的能量。
请问把 变成 最少需要消耗多少能量?
输入格式
本题有多组数据。
对于每组测试,一行一个整数 。
输出格式
一行一个整数,表示最少消耗的能量。
1
4
0
2
提示
。
ACM 实验室开启了一个数字工程项目,希望把正整数 n 通过一些特殊方法变成 1。
可采用的方法有:
每操作一次消耗一个单位的能量。
请问把 n 变成 1 最少需要消耗多少能量?
本题有多组数据。
对于每组测试,一行一个整数 n。
一行一个整数,表示最少消耗的能量。
1
4
0
2
1≤n≤106。