1-100までの素数 - みずぴー日記

30分プログラム、その579。「何も見ずに、1-100までの素数を計算してみよう」という電波を受けとったので、やってみた。
思い付いたのを全部書いて、3つか4つぐらい作ってやるぜー、といきごんで始めてみたけど、2つしか書けなかった。
というか、そもそもエラトステネスの篩ぐらいしか素数計算アルゴリズムを知らなかった。あとは、フェルマーテストとアトキンスの篩ぐらいしか知らないけど、どっちも何か見ながらじゃないと書けないしね。

全部チェックする

1-100まで単純に素数判定をしてる。一応、sqrt(n)までしかチェックしないぐらいの工夫はしてる。

(use srfi-1)

;;; trivial
(define (prime? n)
  (define (loop i)
    (cond
     [(= i 1) #t]
     [(= 0 (modulo n i)) #f]
     [else (loop (- i 1))]))
  (loop (floor->exact (sqrt n))))

(filter prime? (iota 99 2))

エラストテネスの篩

素数計算といえば、エラストテネスの篩。エラストテネスの篩といえば、関数型言語ですよね。

;; sieve
(define (sieve xs)
  (if (eq? xs '())
      '()
      (cons (car xs)
	    (sieve (filter (lambda (n)
			     (not (= 0 (modulo n (car xs)))))
			   (cdr xs))))))
(sieve (iota 99 2))

参考

過去の30分プログラム