comment représenter un nombre comme une somme de 4 nombres premiers?

Question

Voici le problème ( Sommation des Quatre nombres premiers) stipule que:

L'entrée contient un nombre entier N (N <= 10000000) dans chaque ligne. Ceci est le numéro que vous devrez exprimer comme une somme de quatre nombres premiers

Entrée de l'échantillon: 24

36
46

Exemple de sortie:
3 11 3 7 3
7 13 13 11 11 17
7

Cette idée me vient à l'esprit à un premier coup d'oeil

• Trouver tous les nombres premiers ci-dessous N
• Trouvez la longueur de la liste (.length = 4) avec le problème de la partition Entier (Knapsack)

mais la complexité est très mauvais pour cet algorithme, je pense. Ce problème ressemble aussi Goldbach's_conjecture plus. Comment puis-je résoudre ce problème?

Answer 1

Ce problème a un truc simple. Vous pouvez exprimer tous les numéros 3 + 2 + « somme de deux nombres premiers » ou 2 + 2 + « somme de deux nombres premiers » selon la parité du nombre.

pour la "sommation de deux nombres premiers", l'utilisation Conjecture de Goldbach.

Answer 2

Il y a environ 700 mille nombres premiers inférieurs à 10 millions d'euros.

Si le nombre est de réduire encore 2 x 2 de et si réduire impaire 2 + 3 et de trouver les deux autres nombres premiers est pas difficile en raison de la conjecture de Goldbach.

Answer 3

Vous pouvez la mettre en œuvre par le code suivant l'enregistrer beaucoup de temps dans votre programme par marque à chiffres comme constante 2 et 2 ou 2 et 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;
}