Problema
Rotacionar um número leva o primeiro dígito para o final: 197 vira 971 e depois 719. Um primo é circular quando todas as suas rotações também são primas, então 197 é circular. Conte os primos circulares de 2 a limit. Uma rotação pode ser maior que o limite; mesmo assim, ela precisa ser prima.
Implemente circular_primes(limit).
Entrada
limit: o maior número a verificar.
Saída
Retorne quantos primos p ≤ limit são circulares.
Restrições
1 ≤ limit ≤ 100 000
Exemplos
Entrada:
limit = 20
Saída esperada:
expected = 7
Entrada:
long long limit = 20;
Saída esperada:
long long expected = 7;
Entrada:
long limit = 20;
Saída esperada:
long expected = 7;
Explicação
2, 3, 5, 7, 11, 13 (31 é primo) e 17 (71 é primo) são circulares, mas 19 não é (91 = 7 × 13): 7.
Entrada:
limit = 1
Saída esperada:
expected = 0
Entrada:
long long limit = 1;
Saída esperada:
long long expected = 0;
Entrada:
long limit = 1;
Saída esperada:
long expected = 0;
Explicação
Não há primos até 1, então a resposta é 0.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Uma rotação leva o primeiro dígito para o final; um número de d dígitos tem d rotações.
Dica 2
Transformar o número em string facilita a rotação.
Dica 3
As rotações podem ser maiores que o limite, então teste a primalidade delas diretamente.
Complexidade esperada
tempo O(limit × d × √(10^d)) com divisão por tentativa, espaço extra O(d)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.