时间戳

首页 > 解决方案 > 遇到 Prime Indicator Python 代码的递归错误，是否可以重写以避免错误？

python - 遇到 Prime Indicator Python 代码的递归错误，是否可以重写以避免错误？

问题描述

我编辑了一段代码，它为大规模的素数提供反馈。如果数字是素数，它将产生一个以零结尾的两位数，并且将显示两个相同的数字。对于复合数字，它将显示两个不以零结尾的数字。对于复合输入范围 (2^8-2, 2^8)--output__54 54 或素数输入范围 (2^7-2, 2^7)--输出为 __30，您将以这种方式输入数字30

但是我遇到了递归错误。有没有办法重写代码，使其不使用递归或者是否有解决递归的方法。我试过增加系统开销，但没有奏效。

我在尝试 11 时注意到递归错误。

这是代码，如果有人可以帮我编写代码，这样递归就不会出现？

 def isPrime(n):

     isPrime = True

     def is_divisible(n,divisor):
         if n<(divisor-1)*divisor: return False
         if n%divisor==0: return True
         else:
             divisor += 1
             return is_divisible(n,divisor)

     if n==2:
         isPrime = True
     elif is_divisible(n,divisor=2):
         isPrime = False
     return isPrime

 def getNumPrimes(n):
     if n <= 2:
         return 0
     else:
         return isPrime(n-1) + getNumPrimes(n-1)
    
 for n in range(2**11-2,2**11):
     print(getNumPrimes(n))

标签： pythonrecursion

解决方案

您可以使用算法的迭代变体。您可以从底部开始并向上工作，is_divisible()而不是对两者都使用递归。getNumPrimes()

有很多不同的方法可以计算小于或等于给定数字的素数，这篇文章对其中一些用 python 编写的方法进行了基准测试。这是最快的粘贴：

def prime_count(n):
    """Counts number of prime numbers from 0 to n (inclusive)."""
    count = 0
    sieve = [True] * (n + 1)
    for p in range(2, n):
        if sieve[p]:
            count += 1
            for i in range(p, n + 1, p):
                sieve[i] = False
    return count

或者，如果您不想编辑代码，则可以使用该sys模块增加 python 中的递归限制（尽管可能会产生一些意想不到的后果，因此请谨慎操作）：

import sys
sys.getrecursionlimit()
>>> 3000

getNumPrimes(6000)
>>> RecursionError: maximum recursion depth exceeded in comparison

sys.setrecursionlimit(10000)
getNumPrimes(6000)
>>> 783

推荐阅读