Todos os desafios
Médio 0 resolvidos 0% de aceitação

Primos circulares

Conte os primos até um limite cujas rotações de dígitos também são todas primas.

O que você vai aprender

  • Rotacionar os dígitos de um número
  • Verificar uma condição em todas as rotações
  • Contar os números que passam no teste

Problema

Ver original (inglês)

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

Exemplo 1
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.

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

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.