problem 7 - mtsuyuguの日記

10001 番目の素数を求める問題です。

SICP でストリームを勉強してから project euler に戻ってきたときに解いていたのですが、まだ書いていませんでした。

(use util.stream)

(define divisible? (lambda (n d) (= (modulo n d) 0)))
(define square (lambda (x) (* x x)))

(define (integers-starting-from n)
    (stream-cons n (integers-starting-from (+ n 1))))

(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) #t)
          ((divisible? n (stream-car ps)) #f)
          (else (iter (stream-cdr ps)))))
  (iter primes))

(define primes
  (stream-cons
    2
    (stream-filter prime? (integers-starting-from 3))))

(define (p7)
  (stream-ref primes 10000))

(print (p7))