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

Primos circulares

Cuenta los primos hasta un límite cuyas rotaciones de cifras también son todas primas.

Lo que aprenderás

  • Rotar las cifras de un número
  • Comprobar una condición en cada rotación
  • Contar los números que la cumplen

Problema

Ver original (inglés)

Rotar un número consiste en pasar su primera cifra al final: 197 se convierte en 971 y luego en 719. Un primo es circular cuando todas sus rotaciones también son primas, así que 197 es circular. Cuenta los primos circulares del 2 a limit. Una rotación puede ser mayor que el límite, pero aun así tiene que ser prima.

Implementa circular_primes(limit).

Entrada

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

Salida

Devuelve cuántos primos p ≤ limit son circulares.

Restricciones

1 ≤ limit ≤ 100,000

Ejemplos

Ejemplo 1
Entrada:
limit = 20

Salida esperada:
expected = 7
Entrada:
long long limit = 20;

Salida esperada:
long long expected = 7;
Entrada:
long limit = 20;

Salida esperada:
long expected = 7;

Explicación

El 2, 3, 5, 7, 11, 13 (31 es primo) y 17 (71 es primo) son circulares, pero el 19 no lo es (91 = 7 × 13): 7.

Ejemplo 2
Entrada:
limit = 1

Salida esperada:
expected = 0
Entrada:
long long limit = 1;

Salida esperada:
long long expected = 0;
Entrada:
long limit = 1;

Salida esperada:
long expected = 0;

Explicación

No hay primos hasta el 1, así que la respuesta es 0.

Cómo abordarlo

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

Pista 1

Rotar una vez pasa la primera cifra al final; un número de d cifras tiene d rotaciones.

Pista 2

Convertir el número en cadena facilita la rotación.

Pista 3

Las rotaciones pueden ser mayores que el límite, así que comprueba su primalidad directamente.

Complejidad esperada

tiempo O(limit × d × √(10^d)) con división por tentativa, espacio extra O(d)

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.