使用python找不到截斷素數

Question

我厭倦了用python找到特定數字中最小的右截斷素數。當我試圖找到5位數字中最小的右截斷素數時，代碼工作得很好。但是，當我試圖找到6位數字時，python意外退出。

這裏是我的代碼：

def findRTP(digits, currNum = 2): 
    if digits == len(str(currNum)):return currNum 
    else: 
     # if digit % 2 == 0 or digit == 5: 
     #  return findRTP(digits, currNum, digit+1) 
     # elif (digitSum(currNum)+digit)%3 == 0: 
     #  return findRTP(digits, currNum, digit+1) 
     for digit in range(1, 10): 
      currNum = currNum * 10 + digit 
      if isPrime(currNum): 
       result = findRTP(digits, currNum) 
       if result != None: return result 
       else: currNum //=10 
      else: 
       if digit >= 9: 
        currNum //= 10 
        return findRTP(digits, currNum//10) 
       currNum //= 10 
     return None 

# def digitSum(num): 
#  if num == 0: 
#   return 0 
#  else: 
#   return num % 10 + digitSum(num // 10) 

def isPrime(n): 
    if (n < 2): 
     return False 
    if (n == 2): 
     return True 
    if (n % 2 == 0): 
     return False 
    maxFactor = round(n**0.5) 
    for factor in range(3,maxFactor+1,2): 
     if (n % factor == 0): 
      return False 
    return True 

def callWithLargeStack(f,*args): 
    import sys 
    import threading 
    threading.stack_size(2**27) # 64MB stack 
    sys.setrecursionlimit(2**27) # will hit 64MB stack limit first 
    # need new thread to get the redefined stack size 
    def wrappedFn(resultWrapper): resultWrapper[0] = f(*args) 
    resultWrapper = [None] 
    #thread = threading.Thread(target=f, args=args) 
    thread = threading.Thread(target=wrappedFn, args=[resultWrapper]) 
    thread.start() 
    thread.join() 
    return resultWrapper[0] 

print(callWithLargeStack(findRTP, 6)) 

請幫我一下吧。

Answer 1

運行此程序時，它將以退出狀態138結束，這意味着它終止於SIGBUS信號（信號＃10爲128 + 10）。

在這種情況下，這是因爲它超過了線程的堆棧大小。您也可以使用5位版本重現此操作：將堆棧大小更改爲2 ** 16。

threading.stack_size(2**16) # 64MB stack 
... 
print(callWithLargeStack(findRTP, 5)) 

在我的系統上，以這種方式修改程序產生Process finished with exit code 138，就像6位版本一樣。

這裏的簡短答案是，遞歸可能根本不是您嘗試執行的最佳方法。用非遞歸版本代替isPrime並不重要，有些工作你也可以用findRTP來完成。