Project Euler その7

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a^2 + b^2 = c^2
For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

訳

「ピタゴラスの三角数は3つの自然数の組から成り、a<b<cとしたとき、a^2+b^2=c^2となる。例えば3^2+4^2=9+16=25=5^2　a+b+c=1000となるピタゴラスの三角数がたしかに存在する。abcの積を求めよ。」

コード

canditate=[]

for a in xrange(1,500):
    for b in xrange(1,500):
        for c in xrange(1,500):
            if a+b+c == 1000: canditate.append([a,b,c])

for i in canditate:
    if i[0]**2+i[1]**2 == i[2]**2: print i[0]*i[1]*i[2]

遅い（確信）

Problem 10

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

Find the sum of all the primes below two million.

訳

「10以下の素数の和は2+3+5+7=17 である。200万以下の素数の和を求めよ。」

コード

i = 3
prime = [2]
flag = 0

while(1):
    for j in prime:
        if i%j == 0:
            flag = 1
            break
    if flag == 0:
        prime.append(i)
    flag = 0
    if i >= 2000000: break
    i += 1

print sum(prime)

これまた遅い。高速素数判定かprimetable使いたいところ。