[交流] Project Euler 50 欧拉工程 50 题 已有6人参与

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?

4楼: Originally posted by lurencyj at 2012-02-20 17:26:22:
听说python效率比C++差不多慢个100倍。。。哈哈

997651

#!/usr/bin/env python

def generate_primes(n):
    isprimes=[True]*n
    for i in range(2,n):
        if isprimes[i]:
            for j in range(2*i,n,i):
                isprimes[j] = False
    primes=[i for i in range(3,n,2) if isprimes[i]]
    primes.insert(0,2)
    return primes


def euler50(num):
    p=generate_primes(num)
    max_n=1
    while sum(p[:max_n])         max_n+=1
   
    for i in range(max_n,2,-1):
        for j in range(len(p)-i):
            tmp=sum(p[j:j+i])
            if tmp>num:break
            if tmp in p:
                return tmp
        
if __name__ == "__main__":
    print euler50(1000000)