提高质数

Question

从书如何阅读和丹尼尔·索洛待办事项证明的有限产品递归算法，我采取了以下问题：

任何整数n> = 2，可以表示为一个有限的产品素数。

看着书中的证明是用归纳后，我试图然后执行一个算法来验证：

from fermat import fermat 

def first_prime_divisor(n, j): 
    if not fermat(j): 
     return first_prime_divisor(n, j+1) 
    else: 
     if n%j: 
      return first_prime_divisor(n, j+1) 
     else: 
      return j 

def products(n, lista): 


    if n == 2: 
     lista.append(2) 
    elif fermat(n): 
     lista.append(n) 
    else: 
     num = first_prime_divisor(n, 2) 
     lista.append(num) 
     products(n//num, lista) 

凡费尔马是一个已知的素性测试。该代码工作正常，并相应地改变输入列表的状态。 有两个问题，但：

1）我想不会有一个列表变量，而不是将其返回到我

2）函数本身的代码不适合大量的工作（不那么大，例如1531351254251），因为它首先耗尽内存。

你能否给出修复它的建议？ PS：我试图改进我对递归的推理方式，所以我已经解决了使用它的问题。

Answer 1

要删除列表，只需让它直列建设：

def products(n): 
    if n == 2 or fermat(n): 
     return [n] 
    else: 
     num = first_prime_divisor(n, 2) 
     return products(n//num) + [num] 

从这里，主要的问题是你的递归的效率低下;你通过使K-1呼叫找到一个素数除数K来吹出你的堆栈空间。 相反，通过sqrt（num）从n（最近发现的素数）运行支票。在那之后的剩余数字是最后的素数。

然而，最重要的是，您需要打破对递归的依赖，才能通过除数进行迭代。您的系统堆栈不太可能设置为处理大约100万次递归调用的数量级，这就是您仍然在寻找10^12左右的素数的方式。