UVa - 10168 - Summation of Four Primes

UVa - 10168 - Summation of Four Prime

My solution relies on Goldbach's conjecture which states that "Every even integer greater than two can be expressed as the sum of two primes".

This conjecture has been proved right up until 4 * 10 ^ 80.
In this problem, we'll have an N with a maximum value of 10 ^ 7, so we can use the conjecture safely.

The problem simply gives you an integer N and you're required to find four primes that sum up to that integer or output "Impossible" if you can't find them.

sieve is an algorithm that marks prime numbers from 2 to N. It works this way, starts from 2 and marks all multiples of 2 as "not primes", then it goes to 3 and marks all multiples as "not primes" then "4" but found out that "4" is already marked as composite so it doesn't need to mark its multiples which must be already marked and so on.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<bool>* sieve(int n)
{
    vector<bool>* pNums = new vector<bool>(n+1, true);
    vector<bool>& nums = *pNums;
    nums[0] = nums[1] = false;

    for(int i = 2; i * i <= n; ++i)
    {
        if(nums[i])
        {
            for(int j = 2 * i; j <= n; j += i)
            {
                nums[j] = false;
            }
        }
    }

    return pNums;
}

int main(int argc, char *argv[])
{
    const int N = 10000000;
    vector<bool> *pNums = sieve(N);
    vector<bool> &nums = *pNums;

    int n;

    while(cin >> n)
    {
        if(n < 8)
            cout << "Impossible." << endl;
        else
        {
            int remainingSum;

            if(n%2 == 0)
            {
                cout << "2 2 ";
                remainingSum = n - 4;
            }
            else
            {
                cout << "2 3 ";
                remainingSum = n - 5;
            }

            int i;
            for (i = 2; i < remainingSum;++i)
            {
                if(nums[i] && nums[remainingSum-i])
                {
                    cout << i << " " << remainingSum - i << endl;
                    break;
                }
            }
            if(!(nums[i] && nums[remainingSum-i]))
                cout << "Impossible." << endl;
        }
    }
    delete pNums;
    return 0;
}