UVA 10168 - Summation of Four Primes

Problem link

This problem is so easy problem. This time you have a number and you need to find 4 prime numbers but 4 prime numbers sum is your number.

Example: you have a number 11 and 4 prime number is 2, 3, 3, 3. Another Example you have 10 so this time your 4 prime numbers are 2, 2, 3, 3.

so this time fist we can check, our first number is odd or even.

if we show that our number is even then we can print 2 prime numbers first prime number is 2 and the second prime number is 2. and then we decrease 4 from our number,

if we show that our number is odd then we can print 2 prime numbers first prime number is 2 and the second prime number is 3. and then we decrease 5 from our number,

Now we need to just find 2 prime number so now our work is easy. First of all, we can find 1 to 10000000 all prime numbers (Using Sieve ) and save all prime numbers on an array or vector.

So, now we take a prime number (3rd prime) from our array or vector and find our last / 4th number is our number - 3rd prime number.

Then we need to check 4th number is prime or not. if our 4th number is prime this you need to check 3rd and 4th number sum is input number. otherwise, you need to take another prime number from the array or vector and check the same way.

And finally, we check our 3rd number and 4th number sum is input number, this time we need to print this 3rd number and 4th number and BREAK our loop.

Happy coding guys :)

A solution in c++

	#include<bits/stdc++.h>

	using namespace std;

	/// Typedef
	typedef long long ll;

	#define sc1(a) scanf("%lld",&a)
	#define sc2(a,b) scanf("%lld %lld",&a,&b)

	#define pf1(a) printf("%lld\n",a)
	#define pf2(a,b) printf("%lld %lld\n",a,b)

	#define mx 10000007
	#define mod 100000007
	#define PI acos(-1.0)


	int dr[] = {-2,-2,-1,-1,1,1,2,2};
	int dc[] = {-1,1,-2,2,-2,2,-1,1};


	ll checkprime[mx];
	vector<ll>prime;

	void sieve() {

	ll n,i,j;

	for(i=4; i<mx; i+=2) checkprime[i] = 1;
	for(i=3; i*i<=mx; i+=2){
	if(checkprime[i]==0){
	for(j=i*i; j<mx; j+=(i+i)) checkprime[j] = 1; }
	}
	for(i=3; i<mx; i++) if(!checkprime[i]) prime.push_back(i);
	}


	ll checkPrimeNum(ll extra) {

	if(extra<=1)return 0;

	for(ll i = 2; i * i <= extra; i++){
	if(extra % i==0)return 0;
	}
	return extra;
	}

	int main()
	{
	ll tc, t = 1;

	sieve();

	ll num;

	//freopen("/opt/Coding/clion code/output.txt", "w", stdout);

	while (cin >> num){

	if(num < 8){
	cout << "Impossible." << endl;
	continue;
	}
	if(num % 2 == 0){
	cout << "2 2 ";
	num -= 4;
	}
	else{

	cout << "2 3 ";
	num -= 5;
	}

	if(num == 4){
	cout << "2 2" << endl;
	continue;
	}

	ll extra = 0;

	for(ll i = 0; i < num; i++){

	extra = num - prime[i];

	if(prime[i] + checkPrimeNum(extra) == num){
	cout << prime[i] << " " << extra << endl;
	break;
	}
	}

	}

	}