THA-PHÂN RÃ NGUYÊN TỐ

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
int main(){
	int n;
	cin>>n;
	vector<bool>mark(n+1,true);
	vector<int>arr;
	mark[1]=false;
	for(ll i=2;i<=n;i++){
		if(!mark[i])continue;
		arr.push_back(i);
		for(ll j=i*i;j<=n;j+=i){
			mark[j]=false;
		}
	}

	if(mark[n]){
		cout<<n;
		return 0;
	}

	int s=arr.size();
	for(auto x:arr){
		if(n-x==x)continue;
		if(mark[n-x]==true){
			cout<<n-x<<" "<<x<<endl;
			return 0;
		}
	}

	for(int i=0;i<s;i++){
		for(int j=i+1;j<s;j++){
			int x=n-arr[i]-arr[j];
			if(x<=0)break;
			auto it=lower_bound(arr.begin()+j+1,arr.end(),x);
			if(it!=arr.end()&&*it==x){
				cout<<*it<<" "<<arr[j]<<" "<<arr[i];
				return 0;
			}
		}
	}
}