Project Euler - Problem 7

問題

• 原文

  What is the 10001st prime number?

• 日本語訳

  10001 番目の素数を求めよ。

解答

素数判定といえばエラトステネスの篩という有名なアルゴリズムがあります。 それを実装したのが下記のeratosで、与えられたリスト（昇順に並んでいると仮定）を篩にかけ、残った数値をリストにして返します。リストを先頭の要素と残りに分割するというのはHaskellやPerlなどでよく見かけるパターンですが、SchemeでもSRFI-1のcar+cdrを使って簡潔に書けます。 take-primesは与えられた個数以上の素数が得られるまで、リストを拡張しながらeratosを繰り返し適用し、得られたリストから与えられた個数の素数を返します。

(use srfi-1)
(define (eratos xs)
  (define (eratos-1 xs result)
    (if (null? xs) (reverse result)
        (let ((last-num (last xs)))
          (receive (n ns) (car+cdr xs)
                   (if (< last-num (* n n)) (append (reverse result) xs)
                       (let ((not-multiple-of-n?
                              (lambda (m) (not (zero? (modulo m n))))))
                         (eratos-1 (filter not-multiple-of-n? ns)
                                   (cons n result))))))))
  (eratos-1 xs '()))
(define (take-primes num-primes)
  (define (take-primes-1 primes)
    (if (< num-primes (length primes)) (take primes num-primes)
        (take-primes-1 (eratos (append primes
                                       (iota num-primes
                                             (+ (last primes) 2)
                                             2))))))
  (take-primes-1 '(2 3)))
(define (solve)
  (last (take-primes 10001)))
(define (main argv)
  (display (solve))
  (newline))