Tous les défis
Moyen 0 résolus 0 % de réussite

Décomposition de Goldbach

Écrivez un nombre pair comme somme de deux nombres premiers, avec le plus petit premier terme possible.

Ce que vous allez apprendre

  • Écrire un test de primalité par divisions successives qui s'arrête à √n
  • Parcourir les candidats par ordre croissant et s'arrêter au premier qui convient
  • Renvoyer un couple dans l'ordre demandé

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

Exemple 1
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].

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.