How to represent an odd number sum of any three prime numbers.

Codeforces Number Theory Problem: D - Dima and Lisa 

Tutorial:

There is a fact that the distance between adjacent prime numbers isn't big. For n = 10⁹ maximal distanse is 282. So let's find maximal prime p, such that p < n - 1 (we can just decrease n while it's not prime(we can check it in O(sqrt(n) complexity). We know that n - p < 300. Now we have even (because n and p are odd) number n - p and we should divide it into a sum of two primes. As n - p < 300, we can just iterate over small primes P and check if P is prime and n - p - P is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce.

Source Code in C++:

#include<bits/stdc++.h>
using namespace std;
int mark[1000000],PrimeNumber[1000000];
int n = 1000,nprime,limit;
void PrimeNum()
{
    mark[1]=1;

    PrimeNumber[nprime++]=2;

    for(int i=4; i<=n; i+=2)
        mark[i]=1;

    for(int i=3; i<=n; i+=2)
    {
        if(!mark[i])
        {
            PrimeNumber[nprime++]=i;

            if(i<=limit)
            {
                for(int j=i*i; j<=n; j=j+i*2)
                {
                    mark[j]=1;
                }
            }
        }
    }
}
int main()
{
    limit = sqrt(n+1);
    PrimeNum();
    int a,b;
    bool ok=false;
    cin>>a;
    int prime;
    for(int i=a-1;; i--)
    {
        ok =true;
        for(int j=2; j*j<=i; j++)
        {
            if(i%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            prime=i;
            break;
        }
    }
    int need = a - prime,got;


    for(int i=0;; i++)
    {

        got = need - PrimeNumber[i];

        ok =true;
        for(int j=2; j*j<=got; j++)
        {
            if(got%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            b=PrimeNumber[i];
            break;
        }

    }
    if(a==3)
    {
        cout<<1<<"\n"<<3<<endl;
    }
    else if(got==0)
    {
        printf("2\n");
        cout<<prime<<" "<<b<<endl;
    }
    else
    {
        printf("3\n");
        cout<<prime<< " "<<got<< " "<<b<<endl;
    }

    return 0;
}