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()