今日は休日だったので子供の面倒をみつつ、Project Eulerをはじめてみた。pythonで解いてる。今日一日で17問程解いたらjapan ranking 200位丁度になった。

ちょっと悩んだのはproblem 10で200万以下の素数の総和を求めるという問題。

最初は素数リストで割り算してみて割り切れるものがなかったら素数リストにappendという単純な方法でやってみたけど、10万くらいで遅くなってしまった。

というわけで篩で。200万までの奇数リストをつくって篩にかけていく。終了条件は最も大きい素数の二乗が200万を超えるかどうか。 で、できた素数のリストをreduceで畳んでprint

numlist = range(3,2000000,2)

def sieve(nums):
    prime_list = [2]
    while 1:
        prime = nums[0]
        prime_list.append(prime)
        if prime * prime > max(nums):
            prime_list = prime_list + nums[1:]
            break
        else:
            nums = [x for x in nums if x%prime != 0]
    return prime_list

print reduce(lambda x,y: x+y, sieve(numlist))