Project Euler #26 - reciprocal cycles

프로젝트 오일러 26번 문제
1/7 = 0.142857142857145827.... 6자리 145827이 반복된다. 1000보다 작은 n 중 1/n 의 주기가 가장 긴 자연수는?

종이에 풀듯이 하나하나 해 봤다.

def ncycle(n):
    m, s = 1, set()
    while True:
        if n > m:
            if m in s:
                if m == 0: return 0
                else: return len(s)
            s.add(m);
            m *= 10
        else: m %= n

ncycleDic = {}
for n in range(2,1000):
    if ncycle(n) > 10: ncycleDic[n] = ncycle(n)
    
print max(ncycleDic, key=ncycleDic.get)

2, 5 같은 소수는 10진수 표현에서 금방 나누어 떨어진다. 2~1000을 모두 체크하는 대신 소인수 분해해서 2와 5만 남는 경우는 제외해도 된다. 배보다 배꼽이...
3은 좀 특별하다 치고, ncycle(7) = 6
ncycle(13) = 6 , 그런데, ncycle(17) = 16, ncycle(19) = 18, ncycle(23) = 22, ncycle(29) = 28... 종이에 풀듯 나눗셈을 해 보면, ncycle(n) < n인 것은 자명하다. 그럼 1000보다 약간 작은 소수 중에  ncycle(n) = n-1 이 되는 걸 찾으면 되겠군.

def ncycle(n):
    m, s = 1, set()
    while True:
        if n > m:
            if m in s:
                if m == 0: return 0
                else: return len(s)
            s.add(m);
            m *= 10
        else: m %= n

for n in range(997,499,-2):
    if ncycle(n) == n-1:
        print n
        break

처음 코드는 0.1초, 이렇게 바꾸면 0.001초