🚀 go-pugleaf

Newsgroups: fj.sci.math,fj.lang.lisp
In-reply-to: p96952tk@sfc.keio.ac.jp's message of Tue, 1 Oct 1996 17:53:49 
GMT

戸梶＠NIFTYです。

> 中学生である私の弟に、今度「できるだけ大きな素数を求められるプログラム
> を作って提出せよ」という任意の宿題が出たので教えて欲しいと頼まれてしま
> いました。
> エラトステネスのふるい等のアルゴリズムを試したのですが、主に速度の点で
> 納得できず、もう少し調べてみようと考えています。
> 
> どなたか、コンピューターによる素数生成アルゴリズムに関する文献またはア
> ルゴリズムそのものの概略を教えていただけないでしょうか。よろしくお願い
> します。

Mick-Lisp を使って、「エラストネスのふるい」により素数を求める関数を作っ
てみました。*prime-numbers* というグローバル変数に素数のリストを記憶し
ておいて次回の呼出しの時に再利用されます。

(defvar *prime-numbers* (list 2))

(defun primes (max)
  (invoke-for ((n (1- max)))
    (setq n (+ n 2))
    (if (or (<= n (car *prime-numbers*))
            (select-for* ((x *prime-numbers*))
              (zerop (% n x))
              )
            )
        nil
      (setq *prime-numbers* (cons n *prime-numbers*))
      )
    )
  (reverse *prime-numbers*)
  )

(primes 20)
(2 3 5 7 11 13 17 19)

--
戸梶  明夫