[Project Euler] Problem 7 「10001番目の素数」

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.

エラトステネスのふるいを使えば, 答えは求まりそうです.

1. ベクターを用意して, すべての要素を#tにする.
2. 配列の添字が２の倍数になっている要素に#fを設定する.もちろん, 2は#tのまま.
3. ２より大きな範囲で最初に#tとなっている要素の添字を求める.これが次の素数になる.
4. 見つけた素数について, 同様に#fを設定する.
5. ベクターの長さの平方根まで処理をすれば終了.

方針に従い, エラトステネスのふるいを実装します.

(require srfi/1)

(define (sieve pv n)
  (define (loop i)
    (when (< i (vector-length pv))
      (vector-set! pv i #f)
      (loop (+ i n))))
  (loop (+ n n)))

(define (find-prime pv start)
  (cond ((<= (vector-length pv) start) #f)
        ((vector-ref pv start) start)
        (else (find-prime pv (+ start 1)))))

(define (eratosthenes pv)
  (define (loop n)
    (when (and n (< n (sqrt (vector-length pv))))
      (sieve pv n)
      (loop (find-prime pv (+ n 1)))))
  (loop 2))
  
(define (prime-vector n)
  (let ((pv (make-vector (+ n 1) #t)))
    (eratosthenes pv)
    pv))

(define (prime-vect-to-list pv)
  (define (loop ans n)
    (if (< n (vector-length pv))
        (let ((p (find-prime pv n)))
          (if p 
              (loop (cons p ans) (+ p 1)) 
              (reverse ans)))
        (reverse ans)))
  (loop () 2))

計算してみます.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 512 MB.
> (prime-vect-to-list (prime-vector 100))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
> (define pl (prime-vect-to-list (prime-vector 1000000)))
> (length pl)
78498
> (list-ref pl 10000)
104743
>