ホーム - Project Euler

Problem 10¶

Summation of Primes¶

The sum of the primes below $10$ is $2 + 3 + 5 + 7 = 17$.
Find the sum of all the primes below two million.

素数の和¶

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

#!r6rs
#!chezscheme

(import (chezscheme))

(define (eratosthenes-sub1! 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-sub2 table)
  (let-values ([(primes falses) (partition
                                  (lambda (num-or-f)
                                    (if num-or-f
                                      num-or-f
                                      #f))
                                  (vector->list table))])
    primes))

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

(define answer-10
  (apply + (eratosthenes 2000001)))

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