Fácil 0 resueltos 0% de aceptación

Primos gemelos

Enumera todas las parejas de primos gemelos (p, p + 2) hasta un límite.

Lo que aprenderás

  • Marcar los primos hasta un límite con una criba
  • Buscar primos que se diferencian en dos
  • Manejar límites demasiado pequeños para contener alguna pareja

Problema

Ver original (inglés)

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.