как представить число как сумму 4 простых чисел?

Question

Здесь проблема ( Суммирование четырех простых чисел ) гласит:

Вход содержит одно целое число N (N <= 10000000) в каждой строке.Это число, которое вы должны будете выразить как сумму четырех простых чисел </p>

Пример ввода:
24
36
46

Пример вывода:
3 11 3 7
3 7 13 13
11 11 17 7

Эта идея приходит мне в голову на первый взгляд

• Найти все простые числа ниже N
• Найти длину списка (.length = 4) с проблемой целочисленного разбиения (рюкзак)

, но сложность очень плохая для этого алгоритма, я думаю.Эта проблема также выглядит как Goldbach's_conjecture больше.Как я могу решить эту проблему?

Answer 1

Эта проблема имеет простой трюк.Вы можете выразить все числа как 3 + 2 + «сумма двух простых чисел» или 2 + 2 + «сумма двух простых чисел» в зависимости от четности числа.

для «суммы двух простых чисел», используйтеГипотеза Гольдбаха.

Answer 2

Существует около 700 тысяч простых чисел ниже 10 миллионов.

Если число еще меньше, чем 2 x 2 от него, и если нечетное, уменьшите 2 + 3 от него, и найти два других простых числа нетрудно из-за предположения Гольдбаха.

Answer 3

Вы можете реализовать его с помощью следующего кода, это сэкономит много времени в вашей программе, сделав цифру как константу 2 & 2 или 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;
}