Problem Analysis
The task is to find the smallest prime number that belongs to an "eight-prime family." A family is built by taking a number, choosing one digit value that appears in it, and replacing every occurrence of that value simultaneously with each of the digits 0 through 9. This yields up to ten candidate numbers; if eight of them are prime, the family qualifies. The crucial modelling insight is that I replace a digit value (for example, all the asterisk-marked 1s in 56**3), not an arbitrary subset of positions. That distinction collapses what could otherwise be a search over all subsets of digit positions - exponential in the number of digits - into a tiny linear scan: for each prime I need only try a handful of digit values to replace.
A second observation prunes the search further. If a digit value d is the one being replaced, then the largest family that can start with d as its smallest member contains 10 - d numbers - I can replace d with d, d+1, ..., 9. To reach a run of prime_run primes I therefore need 10 - d >= prime_run, that is d <= 10 - prime_run. For an eight-prime family the replaced digit can only be 0, 1, or 2. I iterate primes in ascending order, so the first match is automatically the smallest, and for each prime I try only the permitted low replacement digits. The overall complexity is roughly O(P * D) where P is the count of primes below 10^num_digits and D is the digit length - completely tractable for six-digit numbers.
Solution Approach
Sieve Generation Plus Digit-Replacement Enumeration (Python and C)
Both files implement the same three-phase algorithm and differ only in language idioms.
Phase 1 - prime generation via the Sieve of Sundaram. I produce every prime up to 10^num_digits. The Sundaram sieve marks composite odd numbers: an odd value 2k+1 is composite exactly when k = i + j + 2ij for integers 1 <= i <= j. Every unmarked index i then yields the prime 2i+1, and I prepend 2 manually. I chose Sundaram as a compact alternative to the Sieve of Eratosthenes; either gives a sorted prime list, which is all I need to scan in order.
Phase 2 - candidate enumeration. For each prime I convert it to its decimal digit string. I loop over each permitted replaced digit (characters '0' through '0' + (10 - prime_run), exclusive). If the digit does not appear in the string I skip it - no replacement is possible. Otherwise I substitute every digit from the replaced value up to '9' into all occurrences, building a new number string. I discard any result with a leading zero (which would be a shorter number and not a valid same-length family member), and I count only results that are both prime and >= prime. Counting only forward - members at or above the current prime - ensures families are never double-counted: any smaller member would have triggered the match earlier in the ascending scan.
Phase 3 - primality check. Each candidate is tested with simple trial division up to its square root. Because I test only individual candidates - not a second full sieve - and the numbers are at most six digits, this is more than fast enough. When the forward count equals prime_run, I return the current prime immediately.
Language-specific differences. The Python version expresses the replacement family as a generator inside a tuple comprehension and uses str(prime).replace(...) for substitution - concise and idiomatic. The C version uses snprintf to stringify, builds the replaced string with a manual character loop, and uses atoi to convert back. C stores sieve primes in a heap-allocated array (via calloc/malloc) and frees them after use. The algorithm and pruning are identical; only the mechanics differ.