Problema
La conjetura de Goldbach dice que todo número par mayor que 2 es la suma de dos primos. Nunca se ha demostrado, pero se ha verificado para números muchísimo mayores que los de este problema. A menudo hay varias formas: 28 = 5 + 23 = 11 + 17. Encuentra aquella cuyo primo menor sea lo más pequeño posible.
Implementa goldbach_partition(n).
Probar p = 2, 3, 5, ... y comprobar si n − p es primo encuentra la respuesta rápido, porque casi siempre funciona un p pequeño. Para saber si un número de hasta 10^9 es primo por división de prueba, solo hacen falta divisores hasta aproximadamente 31,623.
Entrada
n: un número par mayor que 2.
Salida
Devuelve [p, q], donde p y q son primos, p + q = n, p ≤ q, y p es el primo más pequeño con el que esto se cumple.
Restricciones
4 ≤ n ≤ 10^9, n es par
Ejemplos
Entrada:
n = 28
Salida esperada:
expected = [5, 23]
Entrada:
long long n = 28;
Salida esperada:
std::vector<long long> expected = {5, 23};
Entrada:
long n = 28;
Salida esperada:
long[] expected = new long[] {5, 23};
Explicación
28 − 2 = 26 y 28 − 3 = 25 no son primos, pero 28 − 5 = 23 sí lo es, así que la respuesta es [5, 23].
Entrada:
n = 4
Salida esperada:
expected = [2, 2]
Entrada:
long long n = 4;
Salida esperada:
std::vector<long long> expected = {2, 2};
Entrada:
long n = 4;
Salida esperada:
long[] expected = new long[] {2, 2};
Explicación
La única opción es 2 + 2, así que la respuesta es [2, 2].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Prueba p = 2, 3, 4, ... y detente en el primer p para el que tanto p como n − p sean primos.
Pista 2
Una prueba de primalidad solo necesita probar divisores hasta la raíz cuadrada.
Pista 3
Como te detienes en el p más pequeño, p ≤ n − p se cumple automáticamente.
Complejidad esperada
tiempo O(k √n), donde k es la cantidad de candidatos probados, espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.