http://codeforces.com/problemset/problem/735/D
题意：给出一个n，这个n可以分解成 n = n1 + n2 + …… + nk，其中k可以取任意数。要使得分解以后所有的n的最大因子（不包括自己本身）的和最小，问最小的和是多少。
思路：比赛的时候想到全部拆成素数是最好的，但是不知道怎么拆，看别人跑的特别快，就知道是数论题，绝望之下试了两发暴力，都是TLE了，GG。早上起来才知道有“哥德巴赫猜想”这个东西。
内容大概是如下两点：
1、所有大于2的偶数可以被分解成两个素数。
2、所有大于7的奇数可以被分解成三个素数。（n-3）为偶数，3是一个素数，所以是三个。
所以知道这个猜想之后就变得简单了：
1、偶数：n为2，答案是1，否则答案是2.
2、奇数：首先，n最少可以拆成三个素数，还有两种情况要考虑：n本身是一个素数的话答案就是1，n-2是一个素数答案就是2（一个奇数可以拆成一个偶数+一个奇数，偶数只有2是素数）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N = ; bool check(int n) {
int tmp = sqrt(n * 1.0);
for(int i = ; i <= tmp; i++) {
if(n % i == ) return false;
}
return true;
} int main() {
int n;
scanf("%d", &n);
int ans;
if(n & ) {
if(check(n)) ans = ;
else if(check(n-)) ans = ;
else ans = ;
} else {
if(n == ) ans = ;
else ans = ;
}
printf("%d\n", ans);
return ;
}