ホーム - Project Euler

Problem 10¶

#!r6rs
#!chezscheme

(import (chezscheme))

(define (sum-prime prime?-table)
  (let* ([len (vector-length prime?-table)]
         [index-list (iota len)]
         [prime?-list (vector->list prime?-table)])
    (fold-left
      (lambda (sum index prime?)
        (if prime?
          (+ sum index)
          sum))
      0
      index-list
      prime?-list)))

(define (eratosthenes-sub! table erase-num)
  (assert (vector-ref table erase-num))
  (let loop ([current (* erase-num 2)])
    (cond
      [(<= (vector-length table) current) table]
      [else
        (vector-set! table current #f)
        (loop (+ current erase-num))])))

(define (eratosthenes num)
  (let ([table (make-vector num #t)]
        [count (isqrt (sub1 num))])
    (vector-set! table 0 #f)
    (vector-set! table 1 #f)
    (let loop ([index 2] [table table])
      (cond
        [(< count index) table]
        [(vector-ref table index)
         (loop (add1 index) (eratosthenes-sub! table index))]
        [else (loop (add1 index) table)]))))

;;; Problem 10
(define answer-10
  (sum-prime (eratosthenes 2000001)))

(printf "10: ~D~%" answer-10)