Problema
A conjectura de Goldbach diz que todo número par maior que 2 é a soma de dois primos. Ela nunca foi demonstrada, mas já foi verificada para números muito maiores que os deste problema. Muitas vezes há mais de uma forma: 28 = 5 + 23 = 11 + 17. Encontre aquela cujo primo menor seja o menor possível.
Implemente goldbach_partition(n).
Testar p = 2, 3, 5, ... e verificar se n − p é primo encontra a resposta rapidamente, porque quase sempre um p pequeno funciona. Para testar a primalidade de um número até 10^9 por divisões sucessivas, basta testar divisores até cerca de 31 623.
Entrada
n: um número par maior que 2.
Saída
Retorne [p, q], onde p e q são primos, p + q = n, p ≤ q, e p é o menor primo para o qual isso funciona.
Restrições
4 ≤ n ≤ 10^9, n é par
Exemplos
Entrada:
n = 28
Saída esperada:
expected = [5, 23]
Entrada:
long long n = 28;
Saída esperada:
std::vector<long long> expected = {5, 23};
Entrada:
long n = 28;
Saída esperada:
long[] expected = new long[] {5, 23};
Explicação
28 − 2 = 26 e 28 − 3 = 25 não são primos, mas 28 − 5 = 23 é, então a resposta é [5, 23].
Entrada:
n = 4
Saída esperada:
expected = [2, 2]
Entrada:
long long n = 4;
Saída esperada:
std::vector<long long> expected = {2, 2};
Entrada:
long n = 4;
Saída esperada:
long[] expected = new long[] {2, 2};
Explicação
A única opção é 2 + 2, então a resposta é [2, 2].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Teste p = 2, 3, 4, ... e pare no primeiro p em que p e n − p sejam ambos primos.
Dica 2
Um teste de primalidade só precisa testar divisores até a raiz quadrada.
Dica 3
Como você para no menor p, a condição p ≤ n − p vem de graça.
Complexidade esperada
tempo O(k √n), onde k é a quantidade de candidatos testados, espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.