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