代碼中的邏輯錯誤？

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風格。