problem26gist.py

import time
start = time.time()

import re

# Returns the length of the recurring cycle of 1/num
def cycle_length(num):
	decimals = str(10**2000 // num)
	r = re.compile(r"([0-9]+?)\1+")				# Looks for non-overlapping repeating sequences
	length = max(r.findall(decimals), key=len)		# Length of longest repeating sequence

	return len(str(length))


# Create a set of primes using a sieve method
primes = []
notPrimes = set()
maxPrime = 1000
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)

maxCycle = 0
maxIndex = 1

for i in primes:
	cycle = cycle_length(i)
	if cycle > maxCycle:
		maxCycle = cycle 
		maxIndex = i

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