Problem 50 - 連続する素数の和

前に作った素数判定が火を噴きそうだ。


Problem 50 - PukiWiki

100万未満の素数を連続する素数の和で表したときに最長になる素数を答える問題。


まずは篩。

(define (make-sieve-of-eratothenes n)
  (letrec ((sieve (make-vector (quotient (+ n 1) 2) #t))
           (limit (sqrt n))
           (check
             (lambda (i step)
               (if (< i n)
                   (begin
                     (vector-set! sieve (quotient i 2) #f)
                     (check (+ i step) step)))))
           (make-table
               (lambda (i)
                 (cond ((> i limit) sieve)
                       ((not (vector-ref sieve (quotient i 2))) (make-table (+ i 2)))
                       (else
                         (check (+ i i i) (+ i i))
                         (make-table (+ i 2))))))
           (prime?
             (lambda (i)
               (or (= i 2)
                   (and (> i 1)
                        (odd? i)
                        (vector-ref sieve (quotient i 2))))))
           (fold (lambda (i f acc)
                   (if (>= i n)
                       acc
                       (fold (+ i 2) f
                             (if (vector-ref sieve (quotient i 2))
                                 (f i acc)
                                 acc))))))
    (make-table 3)
    (lambda (m)
      (case m
            ('prime? prime?)
            ('fold (lambda (f acc) (fold 3 f (f 2 acc))))
            ('to-list (reverse (fold 3 cons (cons 2 '()))))))))

キャッシュ付きなので、素数検索はO(1)

全検索(汗

(define (problem50 n)
  (letrec ((sieve (make-sieve-of-eratothenes n))
           (primes (sieve 'to-list))
           (prime?
             (lambda (n) ((sieve 'prime?) n)))
           (search
             (lambda (p sum len max-sum max-len cont)
               (cond ((or (>= sum n) (null? p)) (cont max-sum max-len))
                     ((prime? sum)
                      (search (cdr p) (+ (car p) sum) (+ len 1) sum len cont))
                     (else
                       (search (cdr p) (+ (car p) sum) (+ len 1) max-sum max-len cont)))))
           (iter
             (lambda (p sum len)
               (if (null? p)
                   (list sum len)
                   (search p 0 0 0 0
                           (lambda (s l)
                             (if (> l len)
                                 (iter (cdr p) s l)
                                 (iter (cdr p) sum len))))))))
    (iter primes 0 0)))


(problem50 100) ; (41 6)
(problem50 1000) ; (953 21)
(problem50 10000) ; (9521 65)
(problem50 100000) ; (92951 183)
(time (problem50 1000000))
; cpu time: 319 real time: 319 gc time: 0
; (997651 543)

高速化としては、

  • 2,3,5...2で始まる場合は、奇数の組合せはありえない。
  • 3.5,7,11...それ以外は奇数の組合せはありえない。

と考えると倍速で回せそうな気もする。