Euler project 26

解答の方針: 普通に循環小数の循節をフェルマーの小定理に基づいて解く

#-*- coding: utf-8 -*-

import random
from datetime import datetime

#素数判定
def is_prime3(q,k=50):
	q = abs(q)
	if q == 2: return True
	if q < 2 or q&1 == 0: return False
	d = (q-1)>>1
	while d&1 == 0:
		d >>= 1
	for i in xrange(k):
		a = random.randint(1,q-1)
		t = d
		y = pow(a,t,q)
		while t != q-1 and y != 1 and y != q-1: 
			y = pow(y,2,q)
			t <<= 1
		if y != q-1 and t&1 == 0:
			return False
	return True

#循環小数の循節を数え上げ
def digit_cycle(x):
	while x % 2 == 0:
		x /= 2
	while x % 5 ==0:
		x /= 5
	if x == 1:
		return 0
	counter = 1
	while 10 ** counter % x != 1:
		counter += 1
	return counter

def Euler26():
	line = [(digit_cycle(x), x) for x in xrange(1000) if is_prime3(x)]
	return max(line)[1]

def main():
	start = datetime.now()
	answer = Euler26()
	end = datetime.now()
	print end - start, answer

if __name__ == "__main__":
	main()