投影Euler#35个圆素数（错误结果为1）

Question

我试图尝试第35个问题的欧拉（click here）。问题是这样的：

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?

所以我用第一个一百万个数创建了一个筛子，得到100万以下的所有素数，并用它来比较素数的旋转结果。在

arr = []

for i in range(2, len(sieve)):
    if sieve[i]:
        sub_arr = retCircular(i)
        count = len(sub_arr)
        carry = 0
        for j in sub_arr:
            if sieve[j]:
                carry += 1
                sieve[j] = False
            else:
                break
        if carry == count:
            for j in sub_arr:
                arr.append(j)

print "Number of circular primes =", len(arr)

这个程序给出了100万以下的循环素数为54，而实际答案是55。有人能帮我解决我的问题吗？在

注：

1. retCircular（n）是一个用户定义的函数，它返回数组中数字的所有循环形式。在
2. “sieve”是一个布尔值数组，在所有主要位置索引中包含True，在所有复合位置索引中包含False。在

p/S，如果有人有更好的方法来解决问题，请告诉我！在

Answer 1

我将在这里使用我的顾问的ESP：你的retCircular方法不能正确地处理重复模式，这使得它错过了repunit（字符串为1的）素数。特别是，retCircular（11）返回[11，11]，这会使您的算法错过作为循环素数的那个数字。以下是我的暴力版本：

def retCircular(prime):
    prime_str = str(prime)
    family = [prime]
    for _ in range(len(prime_str)-1):
        prime_str = prime_str[1:] + prime_str[0]
        child = int(prime_str)
        if child == prime:
            break
        family.append(int(prime_str))
    return family

。。。你的主程序有55个素数：

^{pr2}$