problem51gist.py

import time
start = time.time()

# Given a string in the form 56**3, where * represents all possible digits, return
# True if and only if the size of the prime value family is >= famSize
def size_prime_family(num, famSize, primes):
	firstDigit = 0
	if num[0] == "*":
		firstDigit = 1

	count = 0
	potential = 10 - firstDigit
	for i in range(firstDigit, 10):
		copy = int(num.replace("*",str(i)))
		if copy in primes:
			count += 1
		else:
			potential -= 1
			if potential < famSize:
				return False
	return True

# uses size_prime_family to find the smallest possible family
def find_solution(famSize, primes):
	digits = ["0","*","1","2","3","4","5","6","7","8","9"]
	lastDigit = ["1","3","7","9"]

	for a in digits[1:]:    # first digit not 0
		for b in digits:
			for c in digits:
				for d in digits:
					for e in digits:
						for f in lastDigit:
							num = a + b + c + d + e + f
							if num.count("*") != 3:		# num must contain 3 *
								continue
							if size_prime_family(num, famSize, primes):
								return(num)


# Create a set of primes using a sieve
maxPrime = 1000000
primes = set()
notPrimes = [True] * maxPrime
for i in range(2, maxPrime):
	if notPrimes[i-2]:
		primes.add(i)
		for notPrime in range(i*2 -2, maxPrime, i):	# Add all multiples of i to notPrimes
			notPrimes[notPrime] = False

famSize = 8
print(find_solution(famSize, primes))

print("time: " + str(time.time()-start))