题意：纳税额为金额的最大因数（除了本身）。为了逃税将金额n分为n1+n2+......。问怎样分纳税最少。
哥德巴赫猜想：
任一大于2的偶数都可写成两个质数之和。
质数情况：
任何大于5的奇数都是三个素数之和
因此，如果n是偶数，结果就是2。
如果n是奇数。奇数只能拆成一奇一偶。分为2种情况。一偶是2时，那么如果一奇是质数，结果为2。如果一奇不是质数，那么结果至少为3，由于哥德巴赫猜想，3一定可行的，因此结果就是3。
一偶不是2时，一偶至少要交税2，一奇至少交税1，同样由猜想，结果为3。
//#pragma comment(linker,"/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include <stack> #include <list> using namespace std; const int SZ=1000010,INF=0x7FFFFFFF; typedef long long lon; bool isprime(lon x) { int sq=sqrt(x); for(int i=2;i<=sq;++i) { if(x%i==0)return 0; } return 1; } int main() { std::ios::sync_with_stdio(0); //freopen("d:\\1.txt","r",stdin); lon n; cin>>n; if(isprime(n)) { cout<<1<<endl; } else if((n&1)==0) { cout<<2<<endl; } else { if(isprime(n-2)) { cout<<2<<endl; } else cout<<3<<endl; } return 0; }
codeforces736b Taxes (Codeforces Round #382 (Div. 1))
原文：https://www.cnblogs.com/gaudar/p/9609022.html