Project Euler - Problem 10

問題

• 原文

  Find the sum of all the primes below two million.

• 日本語訳

  200万以下の全ての素数の和を計算しなさい.

解答

素数を探す点はProblem 7と同様ですが、2,000,000以下の素数は148,933個も存在するので計算量は文字通り桁違いです。 アルゴリズムを替えるほどではありませんが、以前のコードは大きなリストを何度もコピーし、filterにかけているので低速です。 ベクタを使ったルックアップ・テーブルを事前に用意し、filterの適用も1回に抑えることで3倍程度高速化しました。2以外の偶数が素数でないのは明らかなので、奇数のみを篩にかけ、後から2とconsしています。

SRFI-17のsetterを使ってベクタの書き換えを抽象化しています。

(use srfi-1)

(define (get-sieve upper-limit)
  (define lookup-table (make-vector (+ upper-limit 1) #t))
  (define (prime? n) (ref lookup-table n))
  (set! (setter prime?) (lambda (n retval) (set! (ref lookup-table n) retval)))
  (set! (prime? 0) #f)
  (set! (prime? 1) #f)
  (let sieve-evens ((i 4))
    (unless (> i upper-limit)
            (set! (prime? i) #f)
            (sieve-evens (+ i 2))))
  (let sieve-odds ((i 3))
    (unless (> (* i i) upper-limit)
            (when (prime? i)
                  (let inner-loop ((j (* i i)))
                    (unless (> j upper-limit)
                            (set! (prime? j) #f)
                            (inner-loop (+ j (* i 2))))))
            (sieve-odds (+ i 1))))
  prime?)

(define (solve)
  (define prime? (get-sieve 2000000))
  (apply + (cons 2 (filter prime? (iota (- 1000000 1) 3 2)))))

(define (main argv)
  (display (solve))
  (newline))