Project Euler 75 - daharuの日記

こちらから問題の日本語訳を見ることができます。
Problem 75 - PukiWiki

$a^2+b^2 = c^2$ を満たす最大公約数が1であるa, b, c はm, n を互いに素な奇数と偶数とすれば
$a = 2 mn,\ b = n^2 - m^2,\ c = m^2+n^2$ と表すことができます。
このとき $a+b+c = 2n(n+m)$ 。
これを利用することで、計算回数をだいぶ減らすことができます。

from math import sqrt, floor
stack = dict([(i,0) for i in range(1, 1500001)])

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a%b)

def Odd_Even(a, b):
    return b%2 == 0 if a%2 == 1 else b%2 == 1

for a in range(1, 1000 ):
    for b in range(1, a+1):
        if gcd(a, b) == 1 and Odd_Even(a, b):
            tmp = 2*a*(a+ b)
            c = 1
            while tmp * c < 1500001:
                stack[tmp * c] += 1
                c += 1

print [stack[s] for s in stack].count(1)