project euler problem10 エラトステネスの篩

200万以下の全ての素数の和を計算しなさい.

とのこと

pythonでやってみた

まずは10万まででテスト

#!/usr/bin/env python

# -*- coding: utf-8 -*-
from sys import exit

import time
MIN = 1

MAX = 100000
ans = long(0)

primeNum = [];
print "START : " + str(time.ctime())
for i in xrange(MIN, MAX+1):

    flg = 0

    j = MIN

    sw = 0

    if i % 2 == 0:

        continue

    # 素数の倍数は素数ではない

    for val in primeNum:

        if i % val == 0:

            sw = 1

            break

    if sw == 1:

        continue

    while j <= i:

        if i%j == 0:

            flg = flg + 1

        j += 1

    if flg == 2 or i == 2:

        ans += long(i)

        primeNum.append(i)
print ans
print "END : " + str(time.ctime()

実行結果

START : Wed Oct 29 11:49:06 2008

454396535

END : Wed Oct 29 11:58:03 2008

10分近くかかってる

200万だと現実的な処理時間じゃないなって思っても自力ではこれが限界でした

んでwikipediaで素数を検索

エラトステネスの篩ってのを発見

ステップ３までは出来てたのか・・・

作り直し

#!/usr/bin/env python

# -*- coding: utf-8 -*-
import time
MIN=1

MAX=2000000
def isPrime(n):

    if n < 2:

        return 0

    if n == 2:

        return 1

    if n % 2 == 0:

        return 0

    i = 3

    while i * i <= n:

        if n % i == 0:

            return 0

        i += 2

    return 1
def main():

    ans = long(0)

    for i in xrange(MIN, MAX+1):

        if isPrime(i) == 1:

            ans += long(i)

    return ans
def execute(func):

    print time.ctime()

    print func()

    print time.ctime()
if __name__ == "__main__":

    execute(main)

おお！200万で1分20秒

    i = 3

    while i * i <= n:

        if n % i == 0:

            return 0

        i += 2

のところがポイントだったみたいね

celeron2Gのマシンにしては結構早かったかな

計算アルゴリズムって深いな・・・