526互联

哥德巴赫猜想（升级版）

发布时间 2023-12-16 13:48:59作者: yufan1102

image

思路：先用素数筛把20000以内的素数筛出来，然后枚举两个素数

//哥德巴赫猜想(升级)
#include<bits/stdc++.h>
using namespace std;
const int N=20005;
bitset<N>vis;
vector<int>p;
void prime(){
	vis[1]=1;
	vis[0]=1;
	for(int i=2;i<=sqrt(N);i++){
		if(!vis[i]){
			p.push_back(i);
			for(int j=2*i;j<=N;j+=i){
				vis[j]=1;
			}
		}
	} 
}
void solve(){
    int n;
    cin>>n;
    prime();
    for(auto i:p){
    	for(auto j:p){
    		int k=n-i-j;
    		if(vis[k])continue;
    		cout<<i<<" "<<j<<" "<<k;
    		return;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	//cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}