Problema
Los primos gemelos son dos números primos que se diferencian en 2, como 11 y 13 o 17 y 19. Encuentra todas las parejas de este tipo cuyo número mayor sea menor o igual que limit.
Implementa twin_primes(limit).
Para límites grandes, obtén todos los primos de una vez con una criba en lugar de probar cada número por separado.
Entrada
limit: el valor máximo que puede tener el primo mayor de una pareja.
Salida
Devuelve una lista de parejas [p, p + 2] en las que ambos números son primos y p + 2 ≤ limit, ordenadas por p de forma ascendente. Si no hay ninguna, devuelve una lista vacía.
Restricciones
0 ≤ limit ≤ 10^6
Ejemplos
Entrada:
limit = 20
Salida esperada:
expected = [
[3, 5],
[5, 7],
[11, 13],
[17, 19]
]
Entrada:
long long limit = 20;
Salida esperada:
std::vector<std::vector<long long>> expected = {
{3, 5},
{5, 7},
{11, 13},
{17, 19}
};
Entrada:
long limit = 20;
Salida esperada:
long[][] expected = new long[][] {
new long[] {3, 5},
new long[] {5, 7},
new long[] {11, 13},
new long[] {17, 19}
};
Explicación
Los primos hasta 20 son 2, 3, 5, 7, 11, 13, 17, 19; los que se diferencian en 2 dan [[3, 5], [5, 7], [11, 13], [17, 19]].
Entrada:
limit = 6
Salida esperada:
expected = [
[3, 5]
]
Entrada:
long long limit = 6;
Salida esperada:
std::vector<std::vector<long long>> expected = {
{3, 5}
};
Entrada:
long limit = 6;
Salida esperada:
long[][] expected = new long[][] {
new long[] {3, 5}
};
Explicación
3 y 5 son primos y 5 ≤ 6, pero 7 supera el límite, así que solo queda [[3, 5]].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Una criba encuentra todos los primos hasta 10^6 mucho más rápido que probar cada número.
Pista 2
Después revisa cada p con p + 2 ≤ limit.
Pista 3
La primera pareja es (3, 5), así que cualquier límite menor que 5 da una lista vacía.
Complejidad esperada
tiempo O(limit log log limit), espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.