リスト修行 素数のリストを求める

調べてみると、約数のリスト高速化には素数が必要だということがわかった。どうやら約数という奴を真面目に求めると結構辛いことがわかってきたぞ。ちょっと失敗だ。

そんなわけでエラトステネスのふるいを書いてみる。参考文献無しで書けるかな。

一回目

リストをふるってみた。

(define (primers n)
  (define (iter l)
    (if (null? l)
        '()
        (cons (car l)
              (iter (filter
                      (lambda (o)
                        (not (zero? (modulo o (car l)))))
                      (cdr l))))))
  (iter (iota (- n 1) 2)))

出来たかなぁ。

(primers 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)

おぉぉぉぉ。素数だ。

でも、リストが空になるまでチェックしなくても(sqrt n)まで見ればいいよね。

修正版

(define (primers n)
  (define (iter l)
    (if (< (sqrt n) (car l))
        l
        (cons (car l)
              (iter (filter
                      (lambda (o)
                        (not (zero? (modulo o (car l)))))
                      (cdr l))))))
  (iter (iota (- n 1) 2)))

(primers 10000)

僕のPCで1万までの素数を計算するのに1秒かからない。25回しかふるってないんだから。

調子に乗って100万まで求めちゃった。

(length (primers 1000000)) ; 78498

100万だと結構時間がかかる。2から100万のなかに素数は8万個位ある。

計算回数を大幅に削減することが出来た。

参考文献無しでもサクッと書けたのには自分でも驚きだ。