Todos os desafios
Médio 0 resolvidos 0% de aceitação

Partição de Goldbach

Escreva um número par como soma de dois primos, usando o menor primeiro primo possível.

O que você vai aprender

  • Escrever um teste de primalidade por divisões sucessivas que para em √n
  • Percorrer os candidatos em ordem crescente e parar no primeiro acerto
  • Retornar um par na ordem pedida

Problema

Ver original (inglês)

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

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

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.