Problème
La conjecture de Goldbach affirme que tout nombre pair supérieur à 2 est la somme de deux nombres premiers. Elle n'a jamais été démontrée, mais elle a été vérifiée bien au-delà des nombres utilisés ici. Il y a souvent plusieurs façons de faire, par exemple 28 = 5 + 23 = 11 + 17. Trouvez celle dont le plus petit nombre premier est le plus petit possible.
Implémentez goldbach_partition(n).
Essayer p = 2, 3, 5, ... en testant si n − p est premier donne vite la réponse, car un petit p convient presque toujours. Pour tester la primalité d'un nombre jusqu'à 10^9 par divisions successives, il suffit d'essayer les diviseurs jusqu'à environ 31 623.
Entrée
n : un nombre pair supérieur à 2.
Sortie
Renvoyez [p, q] où p et q sont premiers, p + q = n, p ≤ q, et p est le plus petit nombre premier pour lequel c'est possible.
Contraintes
4 ≤ n ≤ 10^9, n pair
Exemples
Entrée :
n = 28
Sortie attendue :
expected = [5, 23]
Entrée :
long long n = 28;
Sortie attendue :
std::vector<long long> expected = {5, 23};
Entrée :
long n = 28;
Sortie attendue :
long[] expected = new long[] {5, 23};
Explication
28 − 2 = 26 et 28 − 3 = 25 ne sont pas premiers, mais 28 − 5 = 23 l'est, donc la réponse est [5, 23].
Entrée :
n = 4
Sortie attendue :
expected = [2, 2]
Entrée :
long long n = 4;
Sortie attendue :
std::vector<long long> expected = {2, 2};
Entrée :
long n = 4;
Sortie attendue :
long[] expected = new long[] {2, 2};
Explication
La seule possibilité est 2 + 2, donc la réponse est [2, 2].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Essayez p = 2, 3, 4, ... et arrêtez-vous au premier p pour lequel p et n − p sont tous deux premiers.
Indice 2
Un test de primalité n'a besoin d'essayer les diviseurs que jusqu'à la racine carrée.
Indice 3
Comme vous vous arrêtez au plus petit p, la condition p ≤ n − p est automatiquement respectée.
Complexité attendue
temps O(k √n) où k est le nombre de candidats essayés, espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.