Lispでエラトステネスの篩

Table of Contents

1 目標

エラトステネスの篩のアルゴリズムを用いて 素数のリストを求める.

2 range

まず,2以上n以下の整数のリストを作成するために, range関数を定義する.

1:  (defun range (m n)
2:    (if (> m n)
3:      ()
4:      (cons m (range (+ m 1) n))
5:  ))
(range 2 10)
  (2 3 4 5 6 7 8 9 10)

3 filter

与えられた整数nで割り切れる数をリストxsから取り除く関数 filterを定義する.

1:  (defun filter (n xs)
2:    (if (null xs)
3:      ()
4:      (if (= (% (car xs) n) 0)
5:        (filter n (cdr xs))
6:        (cons (car xs) (filter n (cdr xs)))
7:  )))
(filter 2 (range 2 10))
  (3 5 7 9)

4 sieve

エラトステネスの篩を実装する.

1:  (defun sieve (xs)
2:    (if (null xs)
3:      ()
4:      (cons (car xs) (sieve (filter (car xs) (cdr xs))))
5:  ))
(sieve (range 2 20))
  (2 3 5 7 11 13 17 19)

(sieve (range 2 50))
  (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

5 実行過程

  1. (sieve (range 2 100))
  2. (sieve '(2 3 4 5 6 7 ... 100))
  3. (cons 2 (sieve (filter 2 '(3 4 5 6 7 ... 100))))
  4. (cons 2 (sieve '(3 5 7 9 ... 99)))
  5. (cons 2 (cons 3 (sieve (filter 3 '(5 7 9 ... 99)))))
  6. (cons 2 (cons 3 (sieve '(5 7 11 ... 97))))
  7. (cons 2 (cons 3 (cons 5 (cons 7 ... () ... ))))

6 Clojure

Lispによく似た言語であるClojureでのプログラムを紹介する.

Clojure には, 遅延評価 (lazy evaluation)のメカニズムが備わっており, 無限の長さのリストを取り扱うことが可能になる. 遅延評価は,必要が生じるまで計算を遅延させるというメカニズムである.

Clojureで遅延評価を用いたエラトステネスの篩のプログラムは,以下のようになる (説明は省略).

1:  (defn sieve [xs]
2:    (lazy-seq
3:      (cons (first xs)
4:            (sieve (filter #(not= (rem % (first xs)) 0) (rest xs)))
5:  )))
6:  
7:  (defn primes []
8:    (sieve (iterate inc 2))
9:  )

実行するには,まずClojureを起動してプログラムをロードする.

$ java -cp .:clojure.jar clojure.main
user=> (load-file "sieve.clj")

以下は,最初の10個の素数を求めている. (primes) は素数の無限リストなので,takeでリストの最初の部分を取り出している.

user=> (take 10 (primes))
  (2 3 5 7 11 13 17 19 23 29)

以下は,2000以上となる最初の素数を求めている.

(first (filter #(>= % 2000) (primes)))
  2003

Date: 2017-09-29 21:45:09 JST

Author: 田村直之

Validate XHTML 1.0