I was solving D. Dima and Lisa and I was unable to solve the question by myself after trying for an hour. I knew about Goldbach's Conjecture so I had an idea as to how to solve the problem to some extent leaving behind to find last two primes (for n<=10^9) (after setting first one to 3 among the three primes). (For n>9)

I saw the submissions of some coders and they solved the question exactly as follows for the last two prime numbers.

//the function for prime checking

bool isPrime(int x)
{
    for(int i=2;i*i<=x;i+=1)
    {
        if(x%i==0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    if(n==3)
    {
        cout<<1<<endl;
        cout<<3<<endl;
    }
    else if(n==5)
    {
        cout<<1<<endl;
        cout<<5<<endl;
    }
    else if(n==7)
    {
        cout<<1<<endl;
        cout<<7<<endl;
    }
    else if(n==9)
    {
        cout<<3<<endl;
        cout<<3<<" "<<3<<" "<<3<<endl;
    }
    else
    {
        cout<<3<<endl;
        cout<<3<<" ";
        for(int i=3;2*i+3<=n;i+=2)
        {
            if(isPrime(i)&&isPrime(n-3-i))
            {
                cout<<i<<" "<<n-3-i<<endl;
                break;
            }
        }
    }
    return 0;
}

The code seems to run with an worst case complexity of O(sqrt(n)*n) and in the given question n<=10^9 and still the submissions gets an AC in just 31ms.

Here you go with the solution. My Submission

How is it possible? If I am wrong at finding out the complexity please help and tell how this works?