No.9 Find the product abc

Q:
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

A：
#! /usr/bin/env python
#coding=utf-8

import math
import time

''' method 1
    a,b,c 的范围。abc之间必然存在a<b<c这样类似的关系，假设大小按照这样
    显然a<333 & 333<b<500。a+b>c(三角形)，所以c < 500
'''

t1 = time.time()
l = []
s = 0
for i in range(334,500):
    l.append(i ** 2)

for a in range(1,333):
    for b in range(a,500):
        s = a ** 2 + b ** 2
        if s in l:
            c = math.sqrt(s)
            if (a + b + c) == 1000:
                print "a*b*c = %d*%d*%d = %d" %(a,b,c,a*b*c)
                break
t2 = time.time()
print "time used %s" %str(t2-t1)

''' method 2
    逻辑有一点难理解，把c^2 - b^2 的值作为key，这个值的开方作为value
    (b,b^2) = (c,c^2)
    c++
    这样key的值如果存在的话，就是满足a^2＋b^2=C^2
    再判断是否是符合a+b+c=1000
    faster than method 1
'''
def squares():
    i = 1
    while i < 1000:
        yield (i,i**2)
        i += 1
prev = []
seen = {}
found = False
for (i,isq) in squares():
    for (j, jsq) in prev:
        k = seen.get(isq-jsq)
        if not k: continue
        if i + j + k == 1000:
            print "a*b*c = %d*%d*%d = %d" %(j,k,i,j*k*i)
            found = True
            break
    if found:break
    prev.append((i,isq))
    seen[isq] = i

t3 = time.time()
print "time used: %s" %(t3-t2)