找到主因子太慢或崩潰

我目前正在通過瀏覽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

找到主因子太慢或崩潰

回答

相關問題