Project Euler Problem 050

python Project Euler

http://projecteuler.net/index.php?section=problems&id=50
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050

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

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

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

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

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?
  1. まず素数を足しまくる、100万を超えるまで足す。
  2. 2, 3, 5 .. と小さい素数から順番に引いていく。
  3. 100万未満の数で素数であれば、残りの数列が最大の連続する素数の和。
import math
import itertools

import datetime


def primelist(limit=1000):
    checked = [ True ] * ((limit-1)/2)
    result = [2]
    for i in xrange(len(checked)):
        val = i * 2 + 3
        if checked[i]:
            result.append(val)
            j = val + val + val
            while j < limit:
                checked[(j - 3) / 2] = False
                j += val + val
    return result


def is_prime(n):
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0: return False
    if n < 9: return True
    if n % 3 == 0: return False

    r = math.floor(math.sqrt(n))
    f = 5
    while f <= r:
        if n % f == 0: return False
        if n % (f+2) == 0: return False
        f += 6
    return True


def euler050():
    N = 1000000
    l = primelist(N)
    
    x = 0
    for i in xrange(len(l)):
        if x + l[i] > N: break
        x += l[i]
    stop = i
    print stop
    
    for i in xrange(len(l)):
        if is_prime(x):
            start = i
            print x, (start, stop), sum(l[start:stop])
            break
        x -= l[i]


begin = datetime.datetime.now()
euler050()
end = datetime.datetime.now()
print end - begin

答え: 997651
実行時間: 0.555909秒くらい