[交流] 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?

5楼: Originally posted by wangww2011 at 2012-02-20 21:02:01:
这位同学看样子是被严重误导了，且不说有just-in-time这种技术和很多高新能的函数库，就是全用python也没有很慢啊，况且很多时候是可以用优秀算法提高速度的，你当然会说C也可以用同样的算法啊，是的，但是pytho ...

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)