Project Euler

Wiki »

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

リビジョン 5 (Noppi, 2023/12/27 05:17) → リビジョン 6/8 (Noppi, 2023/12/27 13:42)

[ホーム](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 (make-prime-list num) (sum-prime prime?-table) 
   (let* ([len (vector-length prime?-table)] 
          [index-list (iota len)] 
          [prime?-list (vector->list prime?-table)]) 
     (fold-left 
     
       (lambda (lis iota-num (sum index prime?) 
       
         (if prime? 
         (cons iota-num lis) 
         lis)) 
     '() 
     (iota num) 
     (vector->list (eratosthenes num)))) 
           (+ 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 
   (apply + (make-prime-list (sum-prime (eratosthenes 2000001))) 

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