题解 CF1451A 【Subtract or Divide】
ShineEternal
2020-11-22 07:27:00
## description：
给定一个正整数 $n$，每次你可以进行如下两种操作：
- 将 $n$ 除以一个除自身以外的因数。
- 将 $n$ 减去 $1$。
请求出将 $n$ 变为 $1$ 的最少次数。
- 共 $T$ 组数据，$1\le T\le 10^3$，$1\le n\le 10^9$。
- translate by @
[1289H2051N343O375S8](https://www.luogu.com.cn/user/45475)。
## solution：
这道题目乍一看不知道要循环多少次，我们观察一下样例解释的规律，可以看出几个数字都经过了 $2$。
考虑到任何一个大数在 $-1$ 或自身就直接可以变成 $2$，再用一步就可以变成 $1$，不存在更优的解法。
$1,2,3$ 除外，需要特判。
## code：
```cpp
#include<cstdio>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
if(n==1)
{
printf("0\n");
}
else
if(n==2)
{
printf("1\n");
}
else
if(n==3)
{
printf("2\n");
}
else
if(n%2==1)
{
printf("3\n");
}
else
{
printf("2\n");
}
}
return 0;
}
```