定義ISPRIME函數的麻煩

我對LISP非常陌生，並且正在解決一些初學者問題。我試着定義一個ISPRIME函數，但它似乎沒有正常工作。這裏是我的代碼：定義ISPRIME函數的麻煩

(defun ISPRIME (n &optional (d (- n 1))) 
     (if (= d 0) 
      (return-from ISPRIME t)) 
     (if (= (mod n d) 0) 
      (return-from ISPRIME nil)) 
     (ISPRIME n (- d 1)))

但是一旦運行我的代碼使用值5爲例：

(ISPRIME 5) 
Nil

5應該是一個素數。我懷疑一切都落入：（if（=（mod nd）0）語句中，當它不應該是.d應該繼續遞減，直到達到0並返回true，但它不。看到這裏我的邏輯錯誤是發生

任何及所有的幫助感激

來源

2016-09-16 John Bucher

'（mod 5 1）'。另外，你應該使用['COND']（http://www.lispworks.com/documentation/HyperSpec/Body/m_cond.htm）而不是'IF' +'RETURN-FROM's。 – jkiiski

。在你的代碼中的錯誤：！功能應該停留在1，不爲0，因爲任何數是整除1.簡單地改變函數是這樣：

(defun ISPRIME (n &optional (d (- n 1))) 
     (if (= d 1)       ; <- change from 0 to 1 
      (return-from ISPRIME t)) 
     (if (= (mod n d) 0) 
      (return-from ISPRIME nil)) 
     (ISPRIME n (- d 1)))

但是請注意，你的功能不是很有效的，因爲從好玩的最後一次通話return-from回報

(defun isprime (n &optional (d (- n 1))) 
    (cond ((= d 1) t) 
     ((= (mod n d) 0) nil) 
     (t (isprime n (- d 1)))))

：ction，而不是從「遞歸塔」，所以你的功能，可通過消除它以這種方式，通過使用更緊湊的「條件」 cond，而不是 if，並用結果替代 return-from改寫

這仍然是遞歸的，但對於Common Lisp更具慣用性。當然，我們可以用更高效的迭代版本來轉換此功能，並應用更多的efficient algorithm。但請注意，由於函數爲tail recursive，智能編譯器會自動轉換此函數。

新增

您還可以添加一個初始檢查參數n大於1，例如：

(defun isprime (n &optional (d (- n 1))) 
    (cond ((<= n 1) nil) 
     ((= d 1) t) 
     ((= (mod n d) 0) nil) 
     (t (isprime n (- d 1)))))

來源

2016-09-16 05:37:11 Renzo

@coredump，謝謝，我修改了答案。 – Renzo

既然你是計算一個布爾值，的(if test T NIL)情況下，可以通過test更換更一般地說，結果可能可以表示爲單個布爾表達式。我傾向於發現它們更具可讀性。這裏是公認的答案爲例稍加修改：

(defun is-prime (n &optional (d (1- n))) 
    (or (= d 1) 
     (and (plusp d) 
      (plusp (mod n d)) 
      (is-prime n (1- d)))))

爲了完整，並根據從威爾尼斯的答案，這裏是一個循環的版本：

(defun is-prime (n) 
    (loop 
    for d = 2 then (+ d add) 
    for add = 1 then 2 
    thereis (> (* d d) n) 
    until (= (mod n d) 0)))

和等效DO版本：

(defun is-prime (n) 
    (do ((d 2 (+ d add)) 
     (add 1 2)) 
     ((> (* d d) n) t) 
    (when (zerop (mod n d)) 
     (return nil))))

來源

2016-09-16 07:24:11 coredump

['loop loop finish]]（http://clhs.lisp.se/Body/m_loop_f.htm）（這是由'until'觸發的，AFAICS）沒有明確說明當沒有值被累加時返回的內容，並沒有定義循環結語子句。顯然它會返回NIL，但是，CLHS中有沒有明確說明的地方，你知道嗎？ –

@WillNess最相關的規範部分將是「*除非其他子句貢獻返回值，否則在[6.1.4終止測試子句]（http://www.lispworks.com/）中返回的缺省值爲nil。*」文檔/ lw51/CLHS/Body/06_ad.htm），用於'thereis'子句。這種特殊的組合看起來很好，但我肯定希望得到更正式的保證。 – coredump

我想...感謝報價/鏈接。或者最後一個子句'finally（return NIL）'可以被添加，只是爲了明確。與'（return-from is-prime）'相同，可以寫成'（return nil）'（使用'return'也有助於如果想要重命名函數... :)）。因人而異。 :) –

您不應該使用（尾）遞歸，因爲Common Lisp沒有tail call optimization保證。改爲使用do或loop，或者甚至使用prog和go。

而且算法，總是測試你在增加順序，從開始電位爲約數，並停止當你超過(sqrt n)：

(defun ISPRIME (n) 
    (prog ((d 2))       ; defines implicit block named NIL 
    LOOP 
     (if (> (* d d) n) 
      (return-from ISPRIME t)) ; (return T) also works 
     (if (= (mod n d) 0) 
      (return-from ISPRIME nil)) ; or just (return) 
     (if (= d 2) 
     (incf d 1) 
     (incf d 2)) 
     (go LOOP)))

(return)是與(return nil)和相同與(return-from NIL val)相同。由於prog定義了一個名爲NIL的隱式塊，因此可以使用更短且更一般的調用return來代替。

一個有趣的方式在這裏追求的是用通過過濾的越來越多的供應與此isprime函數創建素的擴展列表，用作除數供應在另一個isprime-p功能，只能通過這些測試它的參數而不是所有的可能性，從而實現另一個算法性能增益。素數列表應根據需要進行擴展。素數只會上升到被測數字的平方根，而素數本身只需要通過最高素數的平方根（即被測數字的第四根）進行測試。

來源

2016-09-16 23:28:12

定義ISPRIME函數的麻煩

回答

相關問題