python - python递归代码中的错误，在用户输入的区间中查找回文素数

Question

我编写了一个递归 Python 程序，附在下面，它打印出一个区间内的回文素数。我不能使用循环（这是分配规则）。在我达到大间隔之前它工作正常。

这是我的代码：

import sys
sys.setrecursionlimit(30000)

#this function places all the numbers between the start and end points into a list and determines whether they are prime numbers by seeing if they have a remainder of 0 when divided, else numbers that dont have remainder of zero are stored.
def check_prime(num_list,number): 
    if num_list==[]:
        print(number)
    else:
        num=num_list[0]        
        if number % num == 0: # if there is a no remainder then not a prime
            pass
        else:
            num_list.pop(0)
            check_prime(num_list,number)

# this checks whether the numbers in the interval are palindromes by comparing the first 'letter' to the last 'letter' for each number and seeing whether they match.
def check_palindrome(nums):
    nums1=nums[::-1]
    if nums1==nums:
        new_list=list(range(2,int(nums)))
        check_prime(new_list,int(nums))

# this takes both functions and only stores the numbers that match in both functions.
def check_done(lists):
    if lists!=[]: # takes numbers not stored (so the numbers that are palindromes and primes)
        check_palindrome(str(lists[0]))
        lists.pop(0)
        check_done(lists)

start_int=int(input("Enter the starting point N: \n"))
ending_int=int(input("Enter the ending point M: \n"))
palindromic_primes = print("The palindromic primes are:") 
list1=list(range(start_int,ending_int+1)) #the list will analyse all numbers from the start point till the end point
check_done(list1)

当进入（起点 10000 和终点 20000）wing IDE 时，出现以下错误：

[evaluate palindromeprimes.py] 输入起点N：10000 输入终点M：20000 回文素数为：aborted（断开）

当我将它输入我的学校汽车制造商时，我得到了这个

Comparing output

Output not correct

The expected output was:
Enter the starting point N:
Enter the ending point M:
The palindromic primes are:
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

Your program produced:
Enter the starting point N: 
Enter the ending point M: 
Segmentation fault

Input supplied to your program:
10000
20000


Differences in the files are as follows:
1,29c1,3

根据一位导师的说法，显然，我需要让我的代码更有效率，但我不知道该怎么做。我看到有人告诉我要考虑素数和因子的性质，例如素数都是奇数。因子成对出现，因此如果数字在某个“中点”之前没有因子，那么它也不会在该“中点”之后有任何因子。但是我不知道它们是什么意思。

标签： python

Answer 1

您可以使用递归来遍历数字范围，方法是将范围一分为二并将左侧和右侧结果相加

当您到达单个值范围时，您对其进行处理以检查它是否是回文（比检查它是否为素数更快）并使用递归来检查它是否也是素数。

您可以通过将除数作为默认参数传递来递归检查素数。第一次迭代可以检查数字是否能被 2 整除，然后递归检查它是否能被 3、5、7、9 ...（奇数）整除。一旦你的除数大于你的数的平方根，那么你就知道它是质数和回文数。这将结束递归并将数字作为一个元素列表返回（将通过数字范围内的递归迭代将其添加到其他元素列表中）

def paloPrimes(first,last,prime=2):
    # recursive iteration from first ro last
    if first<last: 
        mid = (first+last)//2
        return paloPrimes(first,mid) + paloPrimes(mid+1,last)
    # now only have one value to check
    if prime==2: # check palindrome 
        if first < 11 or str(first) != str(first)[::-1]: return []
    if first%prime == 0: return []  # not a prime
    if prime*prime < first: 
        return paloPrimes(first,first,prime+1+prime%2) # recurse for primality
    return [first] # return palindromic prime number

输出：

print(paloPrimes(10000,20000))

[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]

Python 中的递归深度有一个限制，因此范围的大小和数字的大小将受到限制（例如paloPrimes(3998992,3998994)）此函数将使用大约 log2(last-first) + √(last/2) 的深度