how to represent a number as a sum of 4 primes?

Here is the problem (Summation of Four Primes) states that :

The input contains one integer number N (N<=10000000) in every line. This is the number you will have to express as a summation of four primes

Sample Input:

24

36

46

Sample Output:

3 11 3 7

3 7 13 1开发者_StackOverflow中文版3

11 11 17 7

This idea comes to my mind at a first glance

• Find all primes below N
• Find length of list (.length = 4) with Integer Partition problem (Knapsack)

but complexity is very bad for this algorithm I think. This problem also looks like Goldbach's_conjecture more. How can I solve this problem?

This problem has a simple trick. You can express all numbers as 3+2 + "summation of two primes" or 2 + 2 + "summation of two primes" depending on parity of the number.

for the "summation of two primes", use Goldbach's Conjecture.

There are around 700 thousand primes below 10 million.

If the number is even reduce 2 x 2 from it and if odd reduce 2 + 3 from it and finding the other two primes is not difficult because of Goldbach conjecture.

You can implement it by the following code it save a lot of time in your program by make to digit as constant 2 & 2 or 2 & 3 :

int isPrime(int x) {
    int s = sqrt(x);
    for (int i = 2; i <= s; i++) {
        if (x % i == 0) {
            return 0;
        }
    }
    return 1;
}
void Num(int x, int & a, int & b) {
    for (int i = 2; i <= x / 2; i++) {
        if (isPrime(i) && isPrime(x - i)) {
            a = i;
            b = x - i;
            return;
        }
    }
}
int main() {
    int n;
    while (cin >> n) {
        if (n <= 7) {
            cout << "Impossible." << endl;
            continue;
        }
        if (n % 2 !=0) {
            int a, b;
            Num(n -5, a, b);
            cout << "2 3 " << a << " " << b << endl;
        }
        else {
            int a, b;
            Num(n -4, a, b);
            cout << "2 2 " << a << " " << b << endl;
        }
    }
    return 0;
}