素数判定と素数列の列挙。

まずは素数判定

; 指定された整数が素数かどうかを判定する。戻り値はbool。
; 注意としては整数以外を指定しないでください。
; (prime? 2) => #t
; (prime? 4) => #f
(define (prime? number)
    (cond
        ((< number 2) #f)   ; 負の数ならびに1ならば素数ではない
        ((< number 4) #t)   ; 2または3ならば素数
        ((even? number) #f) ; 2を除く偶数の場合素数ではない
        (else               ; 3以上の奇数の場合は試し割りを実行
            (let loop((i 3))
                (if (<= i (sqrt number))
                    (if (= (modulo number i) 0)
                        #f
                        (loop (+ i 2)))
                    #t)))))

　一般的な試し割りですね。2..sqrt(n)にある整数で次々割っていくだけ。

素数列の生成

　次に素数列の生成ですが、まずはSchemeらしくリストとその操作によって実装してみます。なおアルゴリズムは「エラトステネスのふるい」を採用しました。というかそれ以外の方法を知りません……。

; upper以下の整数を生成する。存在しない場合は空リストを返す。
; (make-primes 10) => '(2 3 5 7)
; (make-prime 1) => '()
(define (make-primes upper)
    (cond
        ((< upper 2) '())  ; 負の数および1ならばそれ以下の素数は存在しない
        ((= upper 2) '(2)) ; 2は偶数で唯一素数
        (else              ; 3以上の奇数においてエラトステネスのふるいを実行する
            (let loop ((numbers (iota (+ (quotient (- upper 3) 2) 1) 3 2)) (primes '()))
                (if (> (car numbers) (sqrt upper))
                    (append (cons 2 (reverse primes)) numbers)
                    (loop (remove (lambda (number) (= 0 (modulo number (car numbers))))
                                  (cdr numbers))
                          (cons (car numbers) primes)))))))

　何の工夫もしていないので、正直にいって効率はあまりよろしくない。しかしそれをさしひいても、この単純さは大きなメリットになりうると考えます。とりわけ移植性。このソースコードが動かないSchemeの処理系はさすがにないでしょう。

　ちなみにわたしが思いつく限りで、素数生成を効率化すると以下のようになります。

(use srfi-42) ; do-ecを利用するため<gauche>

; upper以下の整数を生成する。存在しない場合は空リストを返す。
; (make-primes 10) => '(2 3 5 7)
; (make-prime 1) => '()
(define (make-primes upper)
    (let ((bools (make-vector (+ upper 1) #t)))
        (do-ec
            (:range i 2 (+ 1 (inexact->exact (floor (sqrt upper)))))
            (when (vector-ref bools i)
                (do-ec
                    (:range j (+ i i) (+ upper 1) i)
                    (vector-set! bools j #f))))
        (filter
            (cut vector-ref bools <>)
            (iota (- upper 2) 2))))

　アルゴリズムは同じエラトステネスのふるいですが、リストを直接操作することをやめて、素数か否かをベクタと真偽値で管理しています。またif文による条件分岐もできるかぎり排除し、効率アップを図っています――もっともわたしが使う程度では「効率のわるい素数列生成」の性能で十分ですが……。

無限リストとしての素数列

　さてここまでの素数列生成は「ある数値以下の素数をすべて列挙する」都合上、「n番目の素数を求める」というようなタイプの問題に対しては無力――とまではいわなくとも、非常に苦手であることは間違いありません。この欠点を克服するにあたっては素数列を無限リストとして生成する方法が一番簡単そうです。

　そこで最初に提示した素数判定関数prime?を利用して、無限リストを作ってみます。

(use util.stream) ; streamライブラリ<gauche>。stream-iotaなどはsrfiの拡張。

; 無限リストの素数列。
; (stream->list (stream-take primes 10)) => (2 3 5 7 11 13 17 19 23 29)
(define primes
    (stream-cons 2 (stream-filter prime? (stream-iota -1 3 2))))

　無限整数列から素数だけを取り出すというシンプルな出来上がりですね。効率もなかなかのもの。すくなくともわたしの使用には十分です。

　なおエラトステネスのふるいを無限リストに適用することも可能です。効率面はやや劣りますが、抽象度が高く、プログラマの満足度は非常に高いと思われます(なんじゃそりゃ)。

(use util.stream) ; streamライブラリ<gauche>。stream-iotaなどはsrfiの拡張。

; 整数列をふるいにかける。
(define (sieve int-stream)
    (stream-cons
        (stream-car int-stream)
        (sieve
            (stream-remove
                (lambda (i) (zero? (modulo i (stream-car int-stream))))
                (stream-cdr int-stream)))))

; 無限リストの素数列。
; (stream->list (stream-take primes 10)) => (2 3 5 7 11 13 17 19 23 29)
(define primes
    (stream-cons 2 (sieve (stream-iota -1 3 2))))