哥德巴赫猜想

#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
 
 
using namespace std;
const int INF = 0x3f3f3f3f;//?????
typedef long long ll;
typedef long double ld;
typedef pair<ll, int>  pll;
typedef pair<int, int> pii; 
const int N = 1e5+5;
int a[55],b[55],color[N],st[N];ll sum[N];
int cnt;
ll qpow(ll x,ll y,ll mod)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans%mod;
}
int prime(int n)
{
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) return 0;
	}
	return 1;
}
int main()
{
	IOS;
	int n; cin >> n;
	int flag=0;flag=prime(n);
	if(flag==1)
	{
		cout << 1 << endl;
	}
	else 
	{
		if(n%2==0) {
			cout << 2 << endl;
		}
		else 
		{
			flag=0;
			flag=prime(n-2);
			if(flag) cout << 2 << endl;
			else cout << 3 << endl; 
		}
	}
	return 0; 
}