problem47gist.py

#---------------------------- New method. Runs in ~0.23 seconds ----------------------------
import time
start = time.time()

# Create a prime sieve that tracks of the number of prime factors for each composite number
limit = 500000
numFactors = [0] * limit 	# Stores the number of prime factors for composite numbers (0 for primes)
for i in range(2, 10000):
	if numFactors[i-2] == 0:			# if i is prime
		numFactors[i-2] = 1
		for multiple in range(i*2 - 2, limit, i):
			numFactors[multiple] += 1	# Increment number of factors for the multiples of i

for n in range(1, limit-3):
	if numFactors[n] == 4 and numFactors[n+1] == 4 and numFactors[n+2] == 4 and numFactors[n+3] == 4:
		break

print(n+2) 

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

#---------------------------- Old method. Runs in ~2.2 seconds ----------------------------
start = time.time()

# Global dictionary that memoizes factorization
memoized = {}

# Returns the number of distinct prime factors
def num_prime_factors(num, primes):
	global memoized
	copy = num
	factors = 0
	for prime in primes:
		if copy % prime == 0:
			factors += 1
			while copy % prime == 0:
				copy /= prime
		if copy in memoized:
			factors += memoized[copy]
			break
		if prime > copy:
			break

	memoized[num] = factors
	return factors

# Create a set of primes using a sieve method
primes = []
notPrimes = set()
maxPrime = 5000
for i in range(2, maxPrime):
	if not i in notPrimes:
		primes.append(i)
		for notPrime in range(i*2, maxPrime, i):	# Add all multiples of i to notPrimes
			notPrimes.add(notPrime)

num = 1
while True:
	consecutive = 1
	num += 4	# Check every 4th number. If num has 4 prime factors, check num - 3 to num + 3
	if num_prime_factors(num, primes) == 4:
		for i in range(num + 1, num + 4):
			if num_prime_factors(i, primes) == 4:
				consecutive += 1
			else:
				break
		for i in reversed(range(num-3, num)):
			if num_prime_factors(i, primes) == 4:
				consecutive += 1
				num = i
			else:
				break
		if consecutive >= 4:
			break

print(num)

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