题意:已知n元需缴税为n的最大因子x元。现通过将n元分成k份的方式来减少缴税。问通过这种处理方式需缴纳的税费。
分析:
1、若n为素数,不需分解,可得1
2、若n为偶数,由哥德巴赫猜想:一个大于2的偶数可以分解成两个素数的和,可得2
3、若n为奇数,n-2为素数,则为2,否则为3。(因为若为奇数要拆,不能拆成1+偶数,至少拆为2+奇数,若此奇数为素数,则输出为2,否则继续拆成3+偶数,那么结果为3(充分利用哥德巴赫猜想的结论))
#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
typedef long long ll;
typedef unsigned long long llu;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {, , -, };
const int dc[] = {-, , , };
const int MOD = 1e9 + ;
const double pi = acos(-1.0);
const double eps = 1e-;
const int MAXN = + ;
const int MAXT = + ;
using namespace std;
bool judge_prime(int n){
for(int i = ; i <= sqrt(n + 0.5); ++i){
if(n % i == ){
return false;
}
}
return true;
}
int main(){
int n;
while(scanf("%d", &n) == ){
if(judge_prime(n)){
printf("1\n");
continue;
}
if(n % == ){
printf("2\n");
continue;
}
if(n & ){
if(judge_prime(n - )){
printf("2\n");
continue;
}
else{
printf("3\n");
continue;
}
}
}
return ;
}