Problem 35

Problem 35

17 January 2003

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

从题意中知道，这个数一定是有奇数数字组成，getNum35(odds, n)生成n位数的全部有奇数组成的数字，我们用a来保存是否已经计算了该组数字

def getNum35(odds, n):
    if n < 0:
        return
    if n == 1:
        for i in odds:
            yield str(i)
    else:
        for i in odds:
            for j in getNum35(odds, n-1):
                yield str(i)+j

def fun35():
    a = {}
    result = 2#下面我们不计算2和5，所以初始化为2
    odds   = [1,3,7,9]
    for n in range(1,7):
        for num in getNum35(odds, n):
            t   = map(int, num)
            t.sort()
            if a.has_key(str(t)):
                #该数字是否已经计算过
                isCal = False
                for i in a[str(t)]:
                    if num in (i+i):
                        isCal = True
                        break
                if isCal:
                    continue
                   
            isOk = True
            if not isPrime(int(num)):
                continue
            for i in range(1, len(num)):
                k = num[i:]+num[:i]#左移i位
                if not isPrime(int(k)):
                    isOk = False
                    break

            if isOk:
                if a.has_key(str(t)):
                    a[str(t)].append(num)
                else:
                    a[str(t)] = [num]
                #判断num是否只由一个数字组成，比如11
                isSame = True
                for i in num[1:]:
                    if i != num[0]:
                        isSame = False
                        break
                if isSame:
                    result += 1
                else:
                    result += len(num)
    return result

answer is 55
time:0.375