如何优化我的递归Lisp函数？附质因数分解函数代码

我来帮你把这个质因数分解的功能补全并优化一下，先看看你现有的代码，再一步步调整：

首先看你写的初始代码 #

(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 prime-factors-helper (x n) 
  (if (is-prime x) 
      (list x) 
      (if (is-prime n) 
          (if (AND (= (mod x n) 0) (<= n (/ x 2))) 
              (cons n (prime-factors-helper (/ x n) n)) 
              (prime-f... ; 这里代码没写完

问题分析与优化 #

1. 优化is-prime函数 #

你原来的质数判断是从n-1往下递归检查，这种方式效率极低——其实我们只需要检查到√n就足够了，而且从2开始往上检查更合理。我给你调整成更高效的递归版本：

(defun is-prime (n &optional (d 2))
  (cond
    ((<= n 1) nil)          ; 小于等于1的数不是质数
    ((>= d (sqrt n)) t)     ; 如果检查到√n都没找到因数，就是质数
    ((zerop (mod n d)) nil) ; 如果能被d整除，不是质数
    (t (is-prime n (1+ d))))) ; 继续检查下一个除数

2. 补全并优化prime-factors-helper与主函数 #

你的prime-factors-helper逻辑方向是对的，但没写完，而且需要明确初始调用的除数从2开始（最小的质数）。我帮你补全逻辑：

(defun prime-factors-helper (x n)
  (cond
    ((is-prime x) (list x)) ; 如果当前x是质数，直接返回它的单元素列表
    ((and (is-prime n) (zerop (mod x n))) 
     ; 如果n是质数且能整除x，把n加入结果，继续用n试除x/n（处理重复因子，比如12=2*2*3）
     (cons n (prime-factors-helper (/ x n) n)))
    (t (prime-factors-helper x (1+ n))))) ; 否则尝试下一个除数

; 主函数，处理输入合法性，调用helper开始分解
(defun prime-factors (n)
  (if (> n 1)
      (prime-factors-helper n 2)
      nil)) ; 小于等于1的数没有质因数，返回空列表

测试示例 #

你可以试试这些调用，验证功能：

• (prime-factors 12) → 返回 (2 2 3)
• (prime-factors 17) → 返回 (17)（17是质数）
• (prime-factors 100) → 返回 (2 2 5 5)
• (prime-factors 1) → 返回 nil

内容的提问来源于stack exchange，提问作者Benz