1000未満の正の整数dについて、1/dの循環節の長さが最大となるものは何か？

http://projecteuler.net/index.php?section=problems&id=26
問題。
1000未満の正の整数dについて、1/dの循環節の長さが最大となるものは何か？


結構悩んだ。下参照。
http://ja.wikipedia.org/wiki/%E5%BE%AA%E7%92%B0%E5%B0%8F%E6%95%B0


素数の倍数同士は循環節の長さがかぶる可能性がある。
とりあえず素数のみについて計算。かぶるときは小さい方。
計算結果は500以上だったので、これが解。

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

def ChkPn(n):
	i = 2
	while i*i <= n:
		if n%i == 0:
			return False
		i += 1
	return True

def Length(n):
    if not n%2:
        return 1
    if not n%5:
        return 1
    if not ChkPn(n):
        return 1
    m = 1
    while True:
        if (10**m -1) % n == 0:
            return m
        m += 1

def Main():
    s = 0
    n = 0
    for i in xrange(1,1000):
        l = Length(i)
        if l > s:
            s = l
            n = i
    return n

print Main()