Problema
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
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]].
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.