找到主因子太慢或崩溃

我目前正在通过浏览ProjectEuler站点上的一些问题来学习LISP。其中一个问题问这样的：找到主因子太慢或崩溃

的13195是5，7，13和29

号码是多少600851475143的最大质因数的首要因素是什么？

我已经一起报废了Lisp代码。但是，对于9位以上的数字，它非常缓慢。大多数情况下，我从来没有得到一个解决方案，而对于8位数字，大约需要4-5秒。更何况，有时我会得到“HEAP超出”错误。

我的问题是我在运行代码（使用Aquamacs）方面做错了什么？这些代码可以通过哪些方式进行优化以更好地适应手头的任务？更重要的是，如何避免“超过HEAP”碰撞？

代码：

(defun potential-factors (number) 
    (loop for x from 1 to (ceiling (/ number 2)) 
     for y = x 
     collect y)) 

(defun factors (number) 
    (let (prime-factors '()) 
    (loop for x in (potential-factors number) 
      do (if (= (mod number x) 0) 
       (setq prime-factors (cons x prime-factors)))) 
    prime-factors)) 

(defun is-prime (n &optional (d (- n 1))) 
    (if (/= n 1) 
     (or (= d 1) 
      (and (/= (rem n d) 0) 
       (is-prime n (- d 1))))())) 

(defun problem-3 (number) 
    (last (sort (remove-if-not #'is-prime (factors number) :from-end t) #'<)))

来源

2016-11-22 MadPhysicist

谷歌“Eratosthenes筛”为一种方式来制作素数列表。那么你不必为每个潜在因素做这么昂贵的搜索。 – Barmar

@Barmar很好！谢谢！ – MadPhysicist

你认为的(potential-factors 600851475143)的结果是什么？计算结果需要多长时间，结果需要多少内存？

来源

2016-11-22 21:09:34

在最大的素质因素结果？我怀疑它会有5-7位数字。 – MadPhysicist

@MadPhysicist：上面的函数调用的结果是什么？ –

问题是，您在potential-factors中创建了1到n/2之间所有数字的列表。该列表占用大量内存并导致程序崩溃。好消息是，你不需要在列表中累积这些数字，但一次只能使用一个数字。在factors用(loop for x from 1 to (ceiling (/ number 2))替换线(loop for x in (potential-factors number)

应该这样做。

来源

2016-11-22 21:09:53 Leo

我不是数学家，但另一个想法：有关将n除以2的见解似乎是因素成对出现。如果A次B是N，那么A是N的一个因子，所以B必须至少是2。但是这个逻辑可以被扩展，对吗？除以3是什么？一旦你检查了3是否是一个因素，那么就没有必要检查所有大于1/3N的数字。对于4而言，这是一样的。观察结果似乎是你只需要检查A小于或等于B的数字 - 那么它的限制是多少？那么，如果A = B，那么A次B = A次A，这意味着在那种情况下，A是N的平方根。所以我认为你只需要检查和平方根N一样高的值，而不是一直到N/2。

但我不是数学家。

来源

2016-11-22 21:37:01 EvansWinner

是的，这是有效的。我在原始代码中实际上已经有了这个，但是之后它被重写了。我会改变这一点，看看它是否会影响很多表现。 – MadPhysicist

找到主因子太慢或崩溃

回答

相关问题