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

Primos truncáveis

Liste os primos até um limite que continuam primos quando se removem dígitos de qualquer uma das pontas.

O que você vai aprender

  • Remover dígitos de qualquer uma das pontas de um número
  • Testar cada truncamento
  • Reunir os resultados em ordem

Problema

Ver original (inglês)

Pegue 3797. Removendo dígitos pela esquerda, obtemos 797, 97 e 7; removendo pela direita, obtemos 379, 37 e 3. Todos são primos, assim como o próprio 3797. Chamamos um primo assim de truncável pelos dois lados. Primos de um dígito não têm o que remover e não contam. Liste todos os primos truncáveis pelos dois lados de 10 a limit.

Implemente truncatable_primes(limit).

Entrada

limit: o maior número a verificar.

Saída

Retorne os primos em ordem crescente. Se não houver nenhum, retorne uma lista vazia.

Restrições

1 ≤ limit ≤ 100 000

Exemplos

Exemplo 1
Entrada:
limit = 40

Saída esperada:
expected = [23, 37]
Entrada:
long long limit = 40;

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

Saída esperada:
long[] expected = new long[] {23, 37};

Explicação

23 (2, 3) e 37 (3, 7) funcionam; 13 falha porque 1 não é primo e 29 falha porque 9 não é. [23, 37].

Exemplo 2
Entrada:
limit = 10

Saída esperada:
expected = []
Entrada:
long long limit = 10;

Saída esperada:
std::vector<long long> expected = {};
Entrada:
long limit = 10;

Saída esperada:
long[] expected = new long[] {};

Explicação

Abaixo de 10 só há primos de um dígito, e eles não contam: [].

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Remover pela direita é dividir por 10.

Dica 2

Remover pela esquerda é pegar o resto da divisão por uma potência de 10.

Dica 3

Todos os truncamentos até sobrar um único dígito precisam ser primos, assim como o próprio número.

Complexidade esperada

tempo O(limit × d × √limit), espaço extra O(answer)

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.