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 13
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?

回答1:

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.

回答2:

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.

回答3:

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;
}