Project Euler – Problem 60 Solution

Problem

The primes 3, 7, 109, and 673, are quite remark­able. By tak­ing any two primes and con­cate­nat­ing them in any order the result will always be prime. For exam­ple, tak­ing 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, rep­re­sents the low­est sum for a set of four primes with this prop­er­ty.

Find the low­est sum for a set of five primes for which any two primes con­cate­nate to pro­duce anoth­er prime.

Solution

Note: the source code for both solu­tions are avail­able on github here.

 

 

Brute Force

This solu­tion runs in just over 29 sec­onds on my machine, not great, but with­in the 1 minute rule for Euler solu­tions.

 

Using Set inter­sec­tions

Here’s an alter­na­tive solu­tion, using set inter­sec­tions.

This solu­tion is slight­ly more effi­cient, run­ning in just over 17 sec­onds on my machine.