エラトステネスのふるい

継続的に何かをやることが苦手で『関数プログラミングの楽しみ』も中途半端なまま放置しているが、通勤の時間を有効に使うため、何でもいいから簡単なプログラムを1日1つ書いてみることにした。

週末の外出中に思いつき、帰りの電車の中でプレ実践。お題は「エラトステネスのふるいを愚直に実装して素数列を生成する」にした。

言語はなんでもいいのだが、とりあえず慣れているscheme（Gauche）を選んだものの、散々な結果に・・・orz
やはり日頃から鍛えてないとだめですな。

結局、帰宅後に微修正をして以下のような結果になった。

;;; Date: 2011/11/27
;;; エラトステネスのふるいを愚直に実装して素数列を生成する

;; [1] 2に印をつける
;; [2] 2の倍数を消す
;; [3] 次の数3に印をつける
;; [4] 3の倍数を消す
;; [5] 次の数5に印をつける
;; [6] 5の倍数を消す
;; ...

(use srfi-1)

;; 数列lisからpで割り切れる数を除いた数列を返す
(define (remove-multiple p lis)
  (remove (lambda (x) (= (remainder x p) 0)) lis))

;; n以下の素数列を返す
(define (prime-list n)
  (let loop ((src (iota (- n 1) 2 1))
             (res '(2)))
    (let ((w (remove-multiple (car src) (cdr src))))
      (if (null? w)
          (reverse res)
          (loop w (cons (car w) res))))))

答え合わせにとググっていたら、古い記事だがperlでおもしろい解答を見つけた。

次にabigailの傑作の変種。

perl -le '$,=" "; print grep { (1 x $_) !~ /^(11+)\1+$/ } (2..100)'

なんでこれで素数判定できるかは、読者の宿題。

404 Blog Not Found:perl - 100までの素数

気になったのでschemeで書き直してみる。

;;; Date: 2011/11/27
;;; エラトステネスのふるい(正規表現版)
;;; (参考) http://blog.livedoor.jp/dankogai/archives/50534089.html

(use srfi-1)

(define (prime-list-re n)
  (let loop ((src (iota (- n 1) 2 1))
             (res ()))
    (if (null? src)
        (reverse res)
        (loop (remove (lambda (x) (#/^(11+)\1+$/ (make-string x #\1))) (cdr src))
              (cons (car src) res)))))

適宜 #?= を入れながら確認。
素数の倍数がふるいにかけられるように徐々に消えていき、なるほど、確かにエラトステネスのふるいだと納得。