問題
解答
素数を探す点は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))
コメント
コメントを投稿