Fácil 0 resolvidos 0% de aceitação

Primos Gêmeos

Liste todos os pares de primos gêmeos (p, p + 2) até um limite.

O que você vai aprender

  • Marcar os primos até um limite com um crivo
  • Procurar primos com diferença dois
  • Tratar limites pequenos demais para conter algum par

Problema

Ver original (inglês)

Primos gêmeos são dois números primos com diferença 2, como 11 e 13 ou 17 e 19. Encontre todos os pares desse tipo cujo maior número seja no máximo limit.

Implemente twin_primes(limit).

Para limites grandes, encontre todos os primos de uma vez com um crivo, em vez de testar cada número separadamente.

Entrada

limit: o maior valor que o primo maior de um par pode ter.

Saída

Retorne uma lista de pares [p, p + 2] em que os dois números são primos e p + 2 ≤ limit, ordenada por p em ordem crescente. Se não houver nenhum par, retorne uma lista vazia.

Restrições

0 ≤ limit ≤ 10^6

Exemplos

Exemplo 1
Entrada:
limit = 20

Saída esperada:
expected = [
    [3, 5],
    [5, 7],
    [11, 13],
    [17, 19]
]
Entrada:
long long limit = 20;

Saída esperada:
std::vector<std::vector<long long>> expected = {
    {3, 5},
    {5, 7},
    {11, 13},
    {17, 19}
};
Entrada:
long limit = 20;

Saída esperada:
long[][] expected = new long[][] {
    new long[] {3, 5},
    new long[] {5, 7},
    new long[] {11, 13},
    new long[] {17, 19}
};

Explicação

Os primos até 20 são 2, 3, 5, 7, 11, 13, 17, 19; os que estão a 2 de distância dão [[3, 5], [5, 7], [11, 13], [17, 19]].

Exemplo 2
Entrada:
limit = 6

Saída esperada:
expected = [
    [3, 5]
]
Entrada:
long long limit = 6;

Saída esperada:
std::vector<std::vector<long long>> expected = {
    {3, 5}
};
Entrada:
long limit = 6;

Saída esperada:
long[][] expected = new long[][] {
    new long[] {3, 5}
};

Explicação

3 e 5 são primos e 5 ≤ 6, mas 7 passa do limite, então só sobra [[3, 5]].

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Um crivo encontra todos os primos até 10^6 muito mais rápido do que testar cada número.

Dica 2

Depois, verifique cada p com p + 2 ≤ limit.

Dica 3

O primeiro par é (3, 5), então qualquer limite menor que 5 dá uma lista vazia.

Complexidade esperada

tempo O(limit log log limit), espaço extra O(limit)

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.