链接：https://ac.nowcoder.com/acm/problem/14609
来源：牛客网
题目描述
Forever97与未央是一对笔友，他们经常互相写信。有一天Forever97去邮局寄信，发现邮局的收费方式变成了按字收费，收取的费用为总字数除了其自身以外的最大因子。虽然Forever97是一个有情调的人，但他不想因新收费方式而破财，所以他打算把信分成几份寄出去来减少邮费。已知Forever97写的信共有n个字，可以拆成无数封信，也可以不拆，每封信最少为2个字。求Forever97最少需要付多少邮费？
输入描述:
第一行一个正整数T(T<=200)，表示共有T组数据。
第2至第T+1行每行一个正整数n(2<=n<=108)。
输出描述:
对每组数据输出一行，即Forever97最少需要付的邮费。
示例1
输入
复制
3
5
6
9
输出
复制
1
2
2
说明
对于第二组数据，一封6字信可以拆分成两封3字信，各付1邮资。
对于第三组数据，一封9字信可以拆分成一封2字信和一封7字信，各付1邮资。
很明显，找一个数由多少个素数组成。
#include <iostream>
#include<string>
using namespace std;
bool prim(int x)//这个是用来判断是否为素数
{
for (int i = 2; i*i <= x; i++)
if (x%i == 0)
return 0;
return 1;
}
int main()
{
int t, ans = 0;
cin >> t;
while (t--)
{
ans = 0;
int n;
cin >> n;
if (prim(n))
cout << 1 << endl;
else
{
if (n % 2)//奇数
{
if (prim(n - 2))//若减2是素数，那就是2与那个数是素数
cout << 2 << endl;
else//若不为素数e.g.11,则需要拆成2，2，7。//9不为素数
{
cout << 3 << endl;
}
}
else//哥德巴赫猜想大于2的偶数都是可由两个素数组成
{
cout << 2 << endl;
}
}
}
return 0;
}