我有此代码:
def has_divisors(n, i=2):
"""
Check if a number is prime or not
:param n: Number to check
:param i: Increasing value that tries to divide
:return: True if prime, False if not
"""
if n <= 1:
return False
if i + 1 == n:
return True
if n <= 2 and n > 0:
return True
if n % i == 0:
return False
return has_divisors(n, i + 1)
哪个数字是质数,问题在于它可以在输入最大递归深度错误之后检查数字质数是否在+-1500之内。有谁知道如何提高此代码的效率(我不想要完全不同的代码,是的,我知道递归对该功能不是一个好主意,但我必须使用它)谢谢!
我实际上通过添加一个条件来提高了效率:
def has_divisors(n, i=2):
"""
Check if a number is prime or not
:param n: Number to check
:param i: Increasing value that tries to divide
:return: True if prime, False if not
"""
if n <= 1:
return False
if i == n:
return True
if n <= 2 and n > 0:
return True
if i * i > n:
return True
if n % i == 0:
return False
return has_divisors(n, i + 1)
感谢所有尝试提供帮助的人。
从How do I find a prime number using recursion in Python修改功能
这应该具有最大递归部> 1M
两项改进:仅转到sqrt(N),并且仅检查奇数。
def has_divisors(N, i=3):
if N <= 2:
return False
elif N % 2 == 0: # even
return True
elif i * i > N: # tried all divisors to sqrt,
# must be prime
return False
elif (N % i) == 0: # i is a divisor
return True
else: # recursively try the next ( odd) divisor
return has_divisors(N, i + 2)
您不需要对every递归进行基本的取消资格测试,因此为了提高效率,根据您的要求,我会像这样进行投射:
def has_no_divisors(n):
if n <= 2 or n % 2 == 0:
return n == 2
def has_no_divisors_recursive(n, i=3):
if i * i > n:
return True
if n % i == 0:
return False
return has_no_divisors_recursive(n, i + 2)
return has_no_divisors_recursive(n)