Project Euler – Problem 60 Solution

Problem

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Solution

Note: the source code for both solutions are available on github here.

 

 

Brute Force

This solution runs in just over 29 seconds on my machine, not great, but within the 1 minute rule for Euler solutions.

 

Using Set intersections

Here’s an alternative solution, using set intersections.

This solution is slightly more efficient, running in just over 17 seconds on my machine.