10168

Golbach’s Conjecture: Any even number can be expressed as a summation of two prime numbers.

This idea is used to solve the problem.

•  if the number is odd then .ie 49 thn 2,3 and goldbach conjechture of (49-5)
• can be expressed as sum of 2 primes.
• if the number is even then 2,2 and goldbach conjechture of (number-4)

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int arr[10000001];
int prime[5000002][2];

int goldbach_Conjecture(int n)
{
	int x = n/2;
	if(prime[x][0]!=0 && prime[x][1]!=0)
	return prime[x][0];
	for(int i=n-2;i>=2;i--)
	{
		if(arr[i]==0 && n-i>=2 && arr[n-i]==0)
		{
			prime[x][0]=i;
			prime[x][0]=n-i;
			return i;
		}
	}
}

int main()
{
	int N;
	int a,b;
	int k=1;
	arr[0]=1;
	arr[1]=1;
	for(int i=2;i<sqrt(10000001);i++)
	{
		if(arr[i]==0)
		{
			for(int j=i+i;j<10000001;j+=i)
			{
				arr[j]=1;
			}
		}
	}
	while(scanf("%d",&N)!=EOF)
	{
		if(N<8)
		cout<<"Impossible.\n";
		else
		{
			if(N%2)
			{
				cout<<2<<" "<<3<<" ";
				a = goldbach_Conjecture(N-5);
				cout<<a<<" "<<N-5-a<<"\n";
			}
			else
			{
				cout<<2<<" "<<2<<" ";
				b = goldbach_Conjecture(N-4);
				cout<<b<<" "<<N-b-4<<"\n";
			}
		}
	}
	return 0;
}