代码中的逻辑错误？

Question

QUESTION: The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left. NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

我的代码是唯一能够输出前五个这样的数字，并显示以下错误：

Traceback (most recent call last): 
    File "main.py", line 41, in 
    if check(i) and check(rev(i)): 
    File "main.py", line 30, in check 
    if sieve[n]: 
IndexError: list index out of range 

代码：

sieve = [True] * 1000001 # Sieve is faster for 2M primes 
def mark(sieve, x): 
    for i in xrange(x+x, len(sieve), x): 
     sieve[i] = False 
sieve[0],sieve[1]=False,False 
for x in xrange(2, int(len(sieve) ** 0.5) + 1): 
    if sieve[x]: mark(sieve, x) 


def rev(n): 
    s=0 
    while n>0: 
    s=s*10+n%10 
    n/=10 
    return s 

def check(n): 
    flag=1 
    while n>0: 
    if sieve[n]: 
     n/=10 
    else: 
     flag=0 
     break 
    return flag==1 

ctr=0 
i=11 
s=0 
while ctr!=11: 
    if check(i) and check(rev(i)): 
    print i 
    s+=i 
    ctr+=1 
    i+=1 

print s 

lww=raw_input() 

Answer 1

你的算法不正确。您正在寻找素数p，这样p从右到左是可截断的，而reverse(p)是从右到左可截断的。

但是，该问题要求您找到素数p，以便p从右到左是可截断的，而p是从左到右可截断的。 p的可截断性从左到右不等于从右到左的可截断性reverse(p)。

考虑的问题，3797给出的数字 - 这是截去两个方向（等你的代码应该捕获它），但它的反面7973不截去右到左，所以你的代码拒绝。这应该会让你失望。

您需要摆脱reverse（因为这里没有任何用处），而是修改您的检查代码以在两个的方向截断。

---

因为你用完筛你得到一个IndexError - 你的代码正确计算，目前只有5素数p不到1万元，使得p是截去右至左，reverse(p)被截去右至-剩下。由于您当时没有跳出循环（因为ctr < 11），您的代码尝试访问sieve[len(sieve)]，并且命中IndexError。

---

另外 - 这不是真的与你的问题有关 - 我认为你来自C背景或类似的东西。你的代码有点难以阅读，因为它不符合标准的Python风格约定。一旦你为自己解决了这个问题（本着欧拉工程的精神），请看看this gist，以更正你的实施方案：1）使其正确工作;和2.）更接近标准的Pythonic风格。