Question
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?
Haskell
import Data.Function (on)
import Data.List (maximumBy)
primes :: [Int]
= 2 : sieve primes [3,5..] where
primes :ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
sieve (pwhere (h, t) = span (< p*p) xs
isPrime :: Int -> Bool
| n < 1 = False
isPrime n | otherwise = not $ or [n `rem` x == 0 | x <- [2..floor $ sqrt $ fromIntegral n]]
consecutive :: Int -> [Int]
= dropWhile (not . isPrime) $ reverse sums where
consecutive p = takeWhile (< 1000000) $ scanl1 (+) $ dropWhile (< p) primes
sums
main :: IO ()
= print $ head $ maximumBy (compare `on` length) $ map consecutive $ take 10 primes main
$ ghc -O2 -o consecutive-prime-sum consecutive-prime-sum.hs
$ time ./consecutive-prime-sum
real 0m0.003s
user 0m0.000s
sys 0m0.003s
Python
#!/usr/bin/env python
def euler(n):
# Create a candidate list within which non-primes will
# marked as None, noting that only candidates below
# sqrt(n) need be checked.
= list(range(n+1))
candidates = int(n**0.5)
fin
# Loop over the candidates, marking out each multiple.
# If the current candidate is already checked off then
# continue to the next iteration.
for i in range(2, fin+1):
if not candidates[i]:
continue
2*i::i] = [None] * (n//i - 1)
candidates[
# Filter out non-primes and return the list.
return [i for i in candidates[2:] if i]
def main():
= euler(1000000)
primes = 0
largest = []
chain for start in range(10):
= primes[start:]
seq = 0
i = 0
total for prime in seq:
+= prime
total if total > 1000000:
break
+= 1
i if total in primes:
= seq[:i]
c if len(c) > len(chain):
= c
chain print(sum(chain))
if __name__ == "__main__":
main()
$ time python3 consecutive-prime-sum.py
real 0m10.962s
user 0m10.938s
sys 0m0.024s
Ruby
#!/usr/bin/env ruby
require 'mathn'
= Prime.each(10000).to_a
primes = []
longest [0..10].each_with_index { |p, i|
primes= i
j begin
+= 1
j = primes[i..j]
cons = cons.reduce(:+)
sum if sum.prime? && cons.length > longest.length
= cons
longest end
end while sum < 1000000
}
puts longest.reduce(:+)
$ time ruby consecutive-prime-sum.rb
real 0m0.059s
user 0m0.059s
sys 0m0.000s