Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Partición de Goldbach

Escribe un número par como suma de dos primos, con el primer primo lo más pequeño posible.

Lo que aprenderás

  • Escribir una prueba de primalidad por división que se detenga en √n
  • Revisar los candidatos en orden creciente y detenerse en el primero que sirva
  • Devolver una pareja en el orden pedido

Problema

Ver original (inglés)

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.