ホーム - 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)]))))

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

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