Problem Analysis
The structure hiding beneath this problem is a clique in an undirected graph. I treat each prime as a node and draw an edge between two primes p and q exactly when both concatenations - pq and qp - are themselves prime. With that model, "find five primes such that any two concatenate to a prime" becomes "find a clique of size five," and "lowest sum" becomes "the clique whose node sum is minimal." This reframing matters because clique search comes with well-understood pruning strategies, and naming the structure tells me at once how to organise the search.
Two number-theoretic facts make the search tractable. First, I need fast primality testing: concatenating a k-digit and an m-digit prime yields a (k+m)-digit candidate, so for a set of five the candidates stay small enough that trial division up to the square root is plenty fast - that test is O(sqrt(n)) per call. Second, I bound the candidate set: every prime in the answer for a set of length L turns out to be below 10^(L-1), so I generate that prime list once with a Sieve of Sundaram (roughly 10,000 primes for L=5). The dominant cost is the pairwise primality predicate, which I memoize so each pair is tested at most once. Clique search is NP-hard in general, so the worst case is exponential, but aggressive pruning over a small prime set keeps the real running time well under a tenth of a second.
Solution Approach
Cached Depth-First Clique Search (Python and C)
Both files implement the same algorithm. I describe it once and note language differences at the end.
Step 1 - Build the prime set. I sieve all primes up to 10^(set_length-1) with the Sieve of Sundaram. Sundaram marks an odd number 2i+1 as composite whenever its index can be written as i + j + 2ij; the unmarked indices map back to the odd primes, and I prepend 2. I picked Sundaram for variety - it is O(N log log N) like the Sieve of Eratosthenes, and either would serve. The output is returned sorted ascending, which is essential for the canonical search below.
Step 2 - Memoized pair predicate. concatenate_is_prime(a, b) tests that both concatenations are prime. This predicate is expensive relative to the recursion overhead and the same pair is queried across many partial cliques, so I cache it. In Python that is a single functools.lru_cache decoration. In C I hand-build a hash table with separate chaining, canonicalising each key as (min(a,b), max(a,b)) to halve the entries (the predicate is symmetric), folding a multiplicative-XOR mix into 2^20 buckets.
Step 3 - Depth-first extension in ascending order. I begin with each prime as the first clique element, then recursively extend: a candidate may join only if it is strictly greater than the current last element and pairs correctly with every element already chosen. I check the pairing predicate before recursing, so branches that cannot grow into a valid clique are never explored. Requiring strictly increasing values means each unordered set is visited exactly once in sorted form, which both removes duplicate orderings and guarantees the first complete clique found has the minimum sum.
Python specifics. The Python version expresses the nested depth-first search as a chain of generator expressions - solution_pairs feeds extend_solution, which feeds another extend_solution - one nesting level per clique element beyond the first pair. A single next() on the outermost generator pulls only the first complete solution and lazily short-circuits the entire chain.
C specifics. The C version uses a recursive dfs with a global found flag; once set, every active frame returns immediately. It keeps the partial clique in a fixed stack array sol[10] and passes the current depth and the next start index explicitly. The loop bound i <= num_primes - need (where need = target - sol_size) prunes the tail when fewer primes remain than slots left to fill.