Project Euler Problem 010

http://projecteuler.net/index.php?section=problems&id=10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

2000000未満の素数を合計する。
素数は1とその数自体でしか割れない自然数なので、既知の素数で割れなければ素数というのを単純に実装してみた。

import math

def primelist(l=1000):
        
    if l < 2:
        return []
    elif l == 3:
        return [2]
    
    result = [2, 3]
    x = 5
    while x < l:
        limit = math.sqrt(x)
        
        it = iter(result);
        it.next()
        
        for i in it:
            if i > limit:
                result.append(x)
                break
            elif x % i == 0:
                break
        x += 2
    
    return result

l = primelist(2000000)
print sum(l)

8秒弱くらいかかる.. orz

別解

最初の方法だと時間がかかるなー。なんかやだなー。と思って頭をひねってみた。
頭をひねっても何も閃かないので、諦めて寝て翌朝に風呂入ってると延髄がささやいた

　ここで死ぬ定めではないと

否、

　1とその数自体以外で割れるということは、何らかの数の倍数である。つまり素数の倍数は素数でない (ｷﾘｯ

たしかにそうかも知れんと思って書き直した。
2の倍数は素数でないことは明らかなので倍数チェックは奇数のみでOK。

import math

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

l = primelist(2000000)
print sum(l)

断然早い。1/10くらいになった。
ノーベル賞取れるんじゃねーか！！と思ったけど、解説PDFも同じ方法だった。

しかも、閾値の設定の仕方が解説より拙いようなのでまだまだ精進が必要。

答え: 142913828922
実行時間: 0.819012秒くらい