[Project Euler] Problem 10 「素数の和」

10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.
200万以下の全ての素数の和を求めよ.

問題7でエラトステネスのふるいを実装したので, その成果を使います.

1. エラトステネスのふるいを使って200万以下の素数のリストを求める.
2. 求めた整数のリストの和を求める.

手続きは次のとおりです.

(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.
> (fold + 0 (prime-vect-to-list (prime-vector 10)))
17
> (fold + 0 (prime-vect-to-list (prime-vector 2000000)))
142913828922
>