题解 | #Forever97与寄信#

思路

先来结论：任一大于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;
}