You don't have to try all numbers. You can
instead use a different strategy, summed up as
"try appending a digit".

Which digit? Well, a digit such that

- it forms a prime together with your current
last digit
- the prime formed has not occurred in the
number before

This should be done recursively (not
iteratively), because you may run out of options
and then you'd have to backtrack and try a
different digit earlier in the number.

This is still an exponential time algorithm,
but it avoids most of the search space because it
never tries any numbers that don't fit the rule
that every pair of adjacent digits must form a
prime number.