思路
先来结论:任一大于2的整数都可写成三个质数之和。(哥德巴赫猜想) 我们可以知道,如果n是一个质数,那答案就是1,否则我们可以暴力枚举质数p,如果n-p也是质数的话答案就是2,否则是3。 当然也可以不那么暴力的枚举,可由两个质数组成的充要条件是n是偶数或者n-2是素数。
代码
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
const int N=1e8+7;
const int mod=1e9+7;
//int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int t,n,ans;
bool judge(int n){
for(int j=2;j<=sqrt(n);j++) if(n%j==0){
return false;
}
return true;
}
signed main(){
cin>>t;
while(t--){
cin>>n;
if(judge(n)) ans=1;
else if(n%2==0||judge(n-2)) ans=2;
else ans=3;
cout<<ans<<"\n";
}
return 0;
}