Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Primos truncables

Genera la lista de primos hasta un límite que siguen siendo primos al quitarles cifras por cualquiera de los dos extremos.

Lo que aprenderás

  • Quitar cifras por cualquiera de los extremos de un número
  • Comprobar cada truncamiento
  • Reunir los resultados en orden

Problema

Ver original (inglés)

Toma 3797. Si le quitas cifras por la izquierda obtienes 797, 97 y 7; si se las quitas por la derecha, 379, 37 y 3. Todos son primos, igual que 3797. A un primo así lo llamaremos truncable por ambos lados. Los primos de una cifra no tienen nada que quitar y no cuentan. Genera la lista de todos los primos truncables por ambos lados del 10 a limit.

Implementa truncatable_primes(limit).

Entrada

limit: el mayor número que hay que comprobar.

Salida

Devuelve los primos en orden creciente. Si no hay ninguno, devuelve una lista vacía.

Restricciones

1 ≤ limit ≤ 100,000

Ejemplos

Ejemplo 1
Entrada:
limit = 40

Salida esperada:
expected = [23, 37]
Entrada:
long long limit = 40;

Salida esperada:
std::vector<long long> expected = {23, 37};
Entrada:
long limit = 40;

Salida esperada:
long[] expected = new long[] {23, 37};

Explicación

23 (2, 3) y 37 (3, 7) cumplen; 13 no, porque 1 no es primo, y 29 tampoco, porque 9 no lo es. [23, 37].

Ejemplo 2
Entrada:
limit = 10

Salida esperada:
expected = []
Entrada:
long long limit = 10;

Salida esperada:
std::vector<long long> expected = {};
Entrada:
long limit = 10;

Salida esperada:
long[] expected = new long[] {};

Explicación

Por debajo de 10 solo hay primos de una cifra, y esos no cuentan: [].

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Quitar cifras por la derecha es dividir entre 10.

Pista 2

Quitar cifras por la izquierda es tomar el resto módulo una potencia de 10.

Pista 3

Todos los truncamientos, hasta llegar a una sola cifra, deben ser primos, y el número también.

Complejidad esperada

tiempo O(limit × d × √limit), espacio extra O(answer)

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.