Common Lisp でエラトステネスの篩

Common Lisp でエラトステネスの篩をやってみてハマったところ。

• make-list という関数は定義できません。
• null? がないので atom を使った。
• 余りを求める関数は mod 。

;; x から max までのリストを作って返す。
;; (mk-list 1 10) ;=> (1 2 3 4 5 6 7 8 9 10)
(defun mk-list (x max)
  (if (= x max) 
      (list max)
      (cons x (mk-list (+ x 1) max))))

;; 引数のリスト ls から x で割りきれる要素を削除したリストを返す。
;; (delete-factor 2 (mk-list 2 50))
;; => (3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49)
(defun delete-factor (x ls)
  (if (atom ls) ls
    (if (= (mod (car ls) x) 0)
         (delete-factor x (cdr ls))
         (cons (car ls) (delete-factor x (cdr ls))))))

;; エラトステネスの篩
;; (sieve-of-eratosthenes (mk-list 2 100))
;; => (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
(defun sieve-of-eratosthenes (ls)
  (if (atom ls) ls
    (cons (car ls)
          (sieve-of-eratosthenes (delete-factor (car ls) (cdr ls))))))

• null がありました。

CL-USER> (null '())      ;;=> T
CL-USER> (null nil)      ;;=> T
CL-USER> (null '(1 2 3)) ;;=> NIL