codeforces #382 div2 D. Taxes(哥德巴赫猜想)
题意：一个人有n元前，他要交的税是n的最大因子（除n外)，现在这个投机倒把者想把前分成k部分(k为大于等于１的任意值）每部分不能为１，分别交税，问最少交多少税。
思路：要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想
内容是：任何一个大于２的偶数可以写成两个素数的和。
（虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的２３３３
那么任何大于２的偶数，答案就是２
奇数可以分成一个３和一个偶数，答案为３．
不过这可能还不够优，这也是这道题的两个trick所在：
如果该数本身为素数，那么不用分（k取１），答案为１
如果该数减去２为素数，那么答案为２．
/* ***********************************************
Author :111qqz
Created Time :2016年11月29日 星期二 11时36分56秒
File Name :code/cf/#382/D.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6LL n;
7bool prime( LL x)
8{
9 for ( LL i = 2 ; i*i <= x ; i++)
10 {
11 if (x%i==0) return false;
12 }
13 return true;
14}
15LL solve( LL x)
16{
17 if (prime(x)) return 1;
18 if (x%2==0) return 2;
19 if (x%2==1)
20 {
21 if (prime(x-2)) return 2;
22 else return 3;
23 }
24}
25int main()
26{
27 #ifndef ONLINE_JUDGE
28 freopen("code/in.txt","r",stdin);
29 #endif
30 cin>>n;
31 LL ans = solve(n);
32 cout<<ans<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}