Project Euler

Wiki »

Problem 10 » 履歴 » リビジョン 7

リビジョン 6 (Noppi, 2023/12/27 13:42) → リビジョン 7/8 (Noppi, 2023/12/28 07:35)

[ホーム](https://redmine.noppi.jp) - [[Wiki|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万以下の全ての素数の和を求めよ. 

 ```scheme 
 #!r6rs 
 #!chezscheme 

 (import (chezscheme)) 

 (define (eratosthenes-sub1! (make-prime-list num) 
   (fold-left 
     (lambda (lis iota-num prime?) 
       (if prime? 
         (cons iota-num lis) 
         lis)) 
     '() 
     (iota num) 
     (vector->list (eratosthenes num)))) 

 (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-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))] (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) (eratosthenes-sub2 table)] table] 
         [(vector-ref table index) 
          (loop (add1 index) (eratosthenes-sub1! (eratosthenes-sub! table index))] 
         [else (loop (add1 index) table)])))) 

 (define answer-10 
   (apply + (eratosthenes (make-prime-list 2000001))) 

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