牛客--Forever97与寄信（数论，哥德巴赫猜想）

思路：由于收费是按最大因子收费，故拆成素数用的钱比较少（除自身外只有1），若本身是素数就不拆了，收费1元；若不是素数由于n是在10 ^8以内，故可根据哥德巴赫猜想：对于大于2的偶数可以拆成两个素数，对于大于7的奇数可以拆成3个素数；故先判断是否为偶数，若是偶数，拆成两个素数，收费两元；若不是偶数，分两种情况：1. n-2是素数，这样的话就可以拆成2和n-2（2比较特殊，一个是素数的偶数），花费两元；2. n-2不是素数，则把n拆成3个素数，花费3元；

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;bool isprime(int n)
{for(int i=2;i*i<=n;i++){if(n%i==0){return false;}}return true;
}int main()
{int i,j;int n,m;int t;scanf("%d",&t);while(t--){scanf("%d",&n);if(isprime(n)){printf("1\n");}elseif(n%2==0||isprime(n-2)){printf("2\n");}else{printf("3\n");}}return 0;}