我写了一个递归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(机翼IDE时，我得到以下错误：
[评估回文肽.py]输入起点N：10000输入终点M：20000回文素数是：中止(断开连接(
当我把它输入我的学校汽车制造商时，我得到了这个
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
根据一位导师的说法，显然，我需要提高代码的效率，但我不知道该怎么做。我看到有人告诉我要考虑素数和因子的性质，比如素数都是奇数。因子成对出现，所以如果数字在某个"中点"之前没有因子，那么在该"中点"之后也不会有任何因子。但是我不知道他们说的是什么意思。
您可以使用递归来迭代数字的范围，方法是将该范围一分为二，并将左侧和右侧的结果加在一起
当你得到一个单一的值范围时，你会对它进行处理，以检查它是否是回文(比检查它是否为素数更快(，并使用递归来检查它是否也是素数。
您可以通过传递除数作为默认参数来递归检查素性。第一次迭代可以检查数字是否可以被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(倒数第一(+√(倒数第二/2(的深度