python - OSX 不断报告 python 意外退出并中止 python

Question

当我运行这个程序时，我创建了一个使用递归打印回文素数的程序(不允许循环)，苹果报告说 python 意外退出并中止并断开 shell。然而，这只发生在输入相当大的情况下，例如 200 - 800 之间。

这有什么原因吗？

我的代码是:

import sys
sys.setrecursionlimit(30000)
    def isprime(start,end,divisor):
        if start == end:
            return -1
        else:
            if divisor == start:
                a = str(start)
                b = str(start)[::-1]
                if a == b:
                    print(b)            
                return isprime(start+1,end,2)
            elif start%divisor == 0:
                return isprime(start+1,end,2)
            else:
                return isprime(start,end,divisor+1)     

    def main():
        n = eval(input('Enter the starting point N:''\n'))
        m = eval(input('Enter the ending point M:''\n'))
        divisor = 2
        print('The palindromic primes are:')
        primenumbers = isprime(n,m,divisor)

    main()

Answer 1

问题是你在大约 20K 递归时用完了堆栈帧 - 当你测试 400 的数字时，你就达到了这个限制。 IE。每个数字使用了太多堆栈帧。改进这一点的一种方法是测试更少的除数，因为每个除数都会花费一帧，而我们测试的数量超出了必要的范围。 IE。当你应该测试 2 到 sqrt(N) 时，你正在测试 2 到 N(甚至更少......)

另一个问题是，尽管显式返回并且程序期望最后有一个值，但您没有返回任何有用的结果。下面解决了这两个问题:

import sys
import math

sys.setrecursionlimit(30000)

def ispalindrome(x):
    y = str(x)
    return y == y[::-1]

def ispalindromeprime(start, end, divisor=2):

    palindrome_primes = []

    if start == end:
        pass

    elif divisor > int(math.sqrt(start)):
        if ispalindrome(start):
            print(start)  # optional
            palindrome_primes.append(start)     
        palindrome_primes.extend(ispalindromeprime(start+1, end))

    elif start % divisor == 0:
        palindrome_primes.extend(ispalindromeprime(start+1, end))

    else:
        palindrome_primes.extend(ispalindromeprime(start, end, divisor+1))

    return palindrome_primes

def main():
    n = int(input('Enter the starting point N: '))
    m = int(input('Enter the ending point M: '))

    print('The palindromic primes are:')
    numbers = ispalindromeprime(n, m)
    print(numbers)

if __name__ == "__main__":
    main()

这会将限制从 400 左右提高到 2500 左右，并返回回文素数列表:

Enter the starting point N: 2
Enter the ending point M: 2500
The palindromic primes are:
2
3
5
7
11
101
131
151
181
191
313
353
373
383
727
757
787
797
919
929
[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929]

我们可以通过将测试的数字和除数减少一半来进一步推进测试。 IE。将“2”视为特殊情况，仅适用于奇数和除数:

def ispalindromeprime(start, end, divisor=3):

    palindrome_primes = []

    if start >= end:
        pass

    elif start % 2 == 0:
        if start == 2:
            print(start)  # optional
            palindrome_primes.append(start)     
        palindrome_primes.extend(ispalindromeprime(start+1, end))

    elif divisor > int(math.sqrt(start)):
        if ispalindrome(start):
            print(start)  # optional
            palindrome_primes.append(start)     
        palindrome_primes.extend(ispalindromeprime(start+2, end))

    elif start % divisor == 0:
        palindrome_primes.extend(ispalindromeprime(start+2, end))

    else:
        palindrome_primes.extend(ispalindromeprime(start, end, divisor+2))

    return palindrome_primes

这会将您的限制提高到 4500 左右，尽管它找不到更多结果。 (尽管它确实提高了程序的速度。)

更新

我们可以做得更好——将限制推到递归堆栈本身的限制。我们可以更轻松地生成回文并测试它们是否是素数，而不是生成素数并测试它们是否是素数(其他代码保持不变):

def isprime(number, divisor=3):

    if number <= 2 or number % 2 == 0:
        return number == 2

    if divisor > int(math.sqrt(number)):
        return True

    if number % divisor == 0:
        return False

    return isprime(number, divisor+2)

def ispalindromeprime(n, m):

    palindromeprimes = []

    if n == m:
        return palindromeprimes

    if ispalindrome(n) and isprime(n):
        print(n)  # optional
        palindromeprimes.append(n)

    palindromeprimes.extend(ispalindromeprime(n+1, m))

    return palindromeprimes

现在，即使使用递归解决方案，我们也可以超越之前的限制:

Enter the starting point N: 1
Enter the ending point M: 20000
The palindromic primes are:
2
...
929
10301
10501
10601
11311
11411
12421
12721
12821
13331
13831
13931
14341
14741
15451
15551
16061
16361
16561
16661
17471
17971
18181
18481
19391
19891
19991
[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991]

由于我们只需要测试奇数(2 除外)，因此我们可以再次将其加倍:

def ispalindromeprime(n, m):

    palindromeprimes = []

    if n > m:
        return palindromeprimes

    if ispalindrome(n) and isprime(n):
        print(n)  # optional
        palindromeprimes.append(n)

    if n == 1 or n % 2 == 0:
        n -= 1

    palindromeprimes.extend(ispalindromeprime(n+2, m))

    return palindromeprimes

获得更大的结果:

Enter the starting point N: 1
Enter the ending point M: 50000
The palindromic primes are:
2
...
19991
30103
30203
30403
30703
30803
31013
31513
32323
32423
33533
34543
34843
35053
35153
35353
35753
36263
36563
37273
37573
38083
38183
38783
39293
[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293]