Lispっぽく素数判定する？

SICPを読んでいても出てくるprime?という素数判定のための手続き。

思い出したように、これって短く書けるんじゃない？って思ったのでメモ書き。
SICPに出てくるのは確かこんな感じ。

(define (prime? n)
  (define (smallest-divisor n)
    (find-divisor n 2))
  (define (find-divisor n test-divisor)
    (cond
     ((> (square test-divisor) n) n)
     ((divides? test-divisor n) test-divisor)
     (else
      (find-divisor n (+ test-divisor 1)))))
  (define (divides? a b)
    (zero? (modulo b a)))
  (= n (smallest-divisor n)))

ちょっと思いついたように書いてみたらこんな感じ。

(define (prime? n)
  (if (< n 2) #f
      (null? (filter (^x (zero? (modulo n x)))
		     (lrange 2 (+ (div (sqrt n) 1) 1))))))

うん。短い。<追記>
ばばろあさんから突っ込まれたので、ちょこっと修正。

@ayato_p 些細なことだけど (if (< n 2) #f ...) は #f が目障りなので (and (<= 2 n) ...) の方が

2013-06-27 07:37:40 via twicli to @ayato_p

(define (prime? n)
  (and (<= 2 n)
       (null? (filter (^x (zero? (modulo n x)))
		      (lrange 2 (1+ (div (sqrt n) 1)))))))

素数列

なんか検索したらshiroさんの書いた記事がヒットしたので抜粋。

• 「よりClojureらしい素数列」をGaucheで

(use srfi-1)
(use gauche.lazy)

(define (prime? n)
  (not (any zero? (lmap (pa$ mod n) (lrange 2 (+ 1 (/ n 2)))))))

(define (prime-numbers)
  (lfilter prime? (lrange 2)))

これが究極系か！って思った。凄い。

ところで、昨年末に確か素数で盛り上がってましたよね。このあたり。

• Gauche のジェネレータと区間篩で無限素数列を作ろう

ジェネレータとかそのあたり、理解が全然浅いので勉強しなくては。