Heavily inspired by Programming a Pristine World. Also closely related to this challenge.
Let's define a pristine prime as a number which is itself prime, but will no longer be prime if you remove any contiguous substring of N base 10 digits, where 0 < N < digits in number
.
For example, 409 is a pristine prime because 409 itself is prime, but all numbers resulting from removing a substring of 1 digit are not prime:
40
49
09 = 9
and all numbers resulting from removing substrings of length 2 are not prime:
4
9
On the other hand, the prime number 439 is not pristine. Removing the different substrings results in:
43
49
39
4
9
While 49, 39, 4, and 9 are all non-prime, 43 is prime; thus, 439 is not pristine.
2, 3, 5, and 7 are trivially pristine, since they cannot have any substrings removed.
Challenge
Your challenge is to create a program or function that takes in a positive integer N and outputs the Nth pristine prime. The code should finish in under 1 minute on any modern PC for any input up to 50.
The shortest code in bytes wins.
As a reference, here are the first 20 pristine primes:
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
Here is a full list of pristine primes up to 1e7, or N = 376.
Finally, here are two related OEIS entries: