ホーム - Project Euler

Problem 50¶

Consecutive Prime Sum¶

The prime $41$, can be written as the sum of six consecutive primes:

$$41 = 2 + 3 + 5 + 7 + 11 + 13.$$

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains $21$ terms, and is equal to $953$.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

連続する素数の和¶

素数41は6つの連続する素数の和として表せる:

$$41 = 2 + 3 + 5 + 7 + 11 + 13.$$

100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

(import (scheme base)
        (gauche base)
        (math prime)
        (scheme list))

(define temp-primes (primes))

(define (prime? num)
  (assume (exact-integer? num))
  (assume (positive? num))
  (cond
    [(= num 1) #f]
    [(= num 2) #t]
    [(even? num) #f]
    [(= num 3) #t]
    [(zero? (mod num 3)) #f]
    [else
      (let loop ([n6-1 5])
        (let ([n6+1 (+ n6-1 2)])
          (cond
            [(< num
                (* n6-1 n6-1))
             #t]
            [(zero? (mod num n6-1))
             #f]
            [(< num
                (* n6+1 n6+1))
             #t]
            [(zero? (mod num n6+1))
             #f]
            [else
              (loop (+ n6+1 4))])))]))

(define (longest-sequence num)
  (let loop ([sum 0] [current-primes temp-primes] [lis '()])
    (if (<= num (+ sum (car current-primes)))
      (reverse lis)
      (loop (+ sum (car current-primes))
            (cdr current-primes)
            (cons (car current-primes) lis)))))

(define (match-lists num lis)
  (let loop ([lis lis]
             [current-primes (drop-while (cut <= <> (apply max lis))
                                         temp-primes)]
             [result (cons lis '())])
    (if (<= num
            (+ (apply + (cdr lis))
               (car current-primes)))
      (reverse result)
      (loop `(,@(cdr lis) ,(car current-primes))
            (cdr current-primes)
            (cons `(,@(cdr lis) ,(car current-primes))
                  result)))))

(define (prime-sequence num)
  (let loop ([initial-list (longest-sequence num)])
    (or (find (^[lis]
                (prime? (apply + lis)))
              (match-lists num initial-list))
        (loop (drop-right initial-list 1)))))

(define answer-50
  (apply + (prime-sequence 100_0000)))

(format #t "50: ~d~%" answer-50)