Lisp代码没有响应

Question

剧透警报:这是Euler项目第7号的答案.

我正在学习Lisp而我正在使用compileonline.com来运行我的代码.虽然在一个简单的程序上内存不足,所以我切换到桌面版本.但是,即使这样也会耗尽内存.有人能告诉我为什么这么糟糕吗？

在它当前的形式它不会挂起,但如果我将其更改为:

(if (= primecount 10001) 

它挂了.即使是小到1000的东西也会挂起.

(setq current 3)
(setq primecount 1)
(setq primes (list 2))
(setq isprime "yes")

(loop for x from current do
  (list 
    (setq isprime "yes")
    (loop 
      for prime in primes do 
        (if (= (mod current prime) 0) 
          (list (setq isprime nil) (return)) 
          nil
        )
    )
    (if isprime 
      (list 
        (setq primecount (+ primecount 1)) 
        (setq primes (cons current primes)) 
        (if (= primecount 100) 
          (return) 
          nil
        )
      )
      (setq current (+ current 1))
    )
  )
)

(write-line (write-to-string primes))

Answer 1

你可以解释吗

• 该变量X是什么以及为什么它未被使用？

• 做什么叫LIST？

• 你为什么要使用所有这些全局变量？

• 你为什么不定义任何功能？

• 为什么代码迭代所有素数？

这是重构和略微改进的版本,它基于您的代码:

(defun find-primes (n &aux (primes (list 2)) (l-primes primes) (n-primes 1))
  "returns a list of the first n primes"
  (flet ((prime-p (i &aux (limit (isqrt i)))
           "returns T if i is a prime number"
           (loop for prime in primes
                 until (> prime limit)
                 when (zerop (mod i prime))
                 do (return-from prime-p nil))
           t))
    (loop for i from 3
          until (>= n-primes n)
          do (when (prime-p i)
               (setf (cdr l-primes) (list i)
                     l-primes (cdr l-primes))
               (incf n-primes))))
  primes)

(print (find-primes 10000))

以上功能特点:

• 它保留了素数列表,增加了
• 它保留对素数列表的最后一个缺点的引用,以有效地添加到列表的末尾
• 它有一个谓词子函数prime-p,T如果数字是素数则返回
• 谓词使用该函数isqrt来限制要搜索的数字

通过检查N和本地宏来推送到最后它看起来像这样:

(defun find-primes (n &aux (primes (list 2)) (l-primes primes) (n-primes 1))
  "returns a list of the first n primes"
  (check-type n (integer 1))
  (flet ((prime-p (i &aux (limit (isqrt i)))
           "returns T if i is a prime number"
           (loop for prime in primes
                 until (> prime limit)
                 when (zerop (mod i prime))
                 do (return-from prime-p nil))
           t))
    (macrolet ((push-last (obj place)
                 `(setf (cdr ,place) (list ,obj)
                        ,place (cdr ,place))))
      (loop for i from 3
            until (>= n-primes n)
            do (when (prime-p i)
                 (push-last i l-primes)
                 (incf n-primes)))))
  primes)

我们来试试吧:

CL-USER 3 > (time (find-primes 10000))
Timing the evaluation of (FIND-PRIMES 10000)

User time    =        0.052
System time  =        0.000
Elapsed time =        0.044
Allocation   = 292192 bytes