Fortemente inspirado pela programação de um mundo intocado . Também intimamente relacionado a esse desafio .
Vamos definir um primo primitivo como um número que é primo em si, mas não será mais primo se você remover qualquer substring contíguo dos N dígitos da base 10, onde 0 < N < digits in number.
Por exemplo, 409 é um primo primitivo porque o próprio 409 é primo, mas todos os números resultantes da remoção de uma substring de 1 dígito não são primos:
40
49
09 = 9
e todos os números resultantes da remoção de substrings de comprimento 2 não são primos:
4
9
Por outro lado, o número primo 439 não é primitivo. A remoção das diferentes substrings resulta em:
43
49
39
4
9
Enquanto 49, 39, 4 e 9 são todos não primos, 43 é primo; assim, 439 não é primitivo.
2, 3, 5 e 7 são trivialmente intocadas, pois não podem ter substrings removidos.
Desafio
Seu desafio é criar um programa ou função que receba um número inteiro positivo N e produza a enésima primitiva primitiva. O código deve terminar em menos de 1 minuto em qualquer PC moderno para qualquer entrada de até 50.
O código mais curto em bytes vence.
Como referência, aqui estão os 20 primeiros números primos:
N Pristine prime
1 2
2 3
3 5
4 7
5 11
6 19
7 41
8 61
9 89
10 409
11 449
12 499
13 821
14 881
15 991
16 6299
17 6469
18 6869
19 6899
20 6949
Aqui está uma lista completa de números primos primitivos até 1e7 ou N = 376.
Finalmente, aqui estão duas entradas relacionadas do OEIS:
fonte