an interesting problem

[Paul Dale]

There can't be an even digit (or zero) since putting that digit in the final position results in a composite number. Likewise, we can't have a five. That leaves: 1, 3, 7 & 9 as possible digits.

Since we're not allowed repeated digits we have to check:

Code:

137
139
179
379

For each of these four we need to check all digit permutations:

Code:

137
173
317
371
713
731

139
193
319
391
913
931

179
197
719
791
917
971

379
397
739
793
937
973

So twenty four possibilities here. However by judiciously choosing composite numbers first, we can do it in with four tries

Code:

371
319
791
793

More realistically, by starting at the top of each list of six and stopping when we find a composite, we have to make fifteen primality checks.

- Pauli