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