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
- the prime formed has not occurred in the
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