AstroBlog

宇宙系大学院生の戯言

Project Euler 10「素数の和」をPython3で書いてみた[解答]

SPONSORED LINK

問題文

10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.

200万以下の全ての素数の和を求めよ.

シンプルな問題文ですね。

ちなみにProject Eulerの日本語訳サイトはこちらです。
Project Euler - PukiWiki

Pythonでの解答はこのサイトに載っています。
Project Euler: Python solutions

ただ、このサイトのPythonのコードはかなり難しい書き方をしています。

こちらの方のコードを参考にさせていただきました。
http://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f

def primesとしてオブジェクトを作るとなんとなく見やすいですね。

import math

# 0以上x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2:return []
    
    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない
    
    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break  #  数字が平方根より大きければbreak
        if prime == 0: continue  #  数字が0ならば続ける
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
            
    return [prime for prime in primes if prime != 0]

if __name__ == '__main__':
    print(sum(primes(2000000)))

実行結果

142913828922