Euler Solution 75

From ProgSoc Wiki

(Difference between revisions)
Jump to: navigation, search
(Python by Althalus)
(Python by Althalus)
Line 5: Line 5:
= Solutions for Euler Problem 75 =
= Solutions for Euler Problem 75 =
== Python by Althalus ==
== Python by Althalus ==
-
Runtime: 53.27s
+
Runtime: 22.14s
  def gcd(a,b):
  def gcd(a,b):

Revision as of 07:29, 22 July 2010

Euler Problem 75

Given that L is the length of the wire, for how many values of L 1,500,000 can exactly one integer sided right angle triangle be formed?

Solutions for Euler Problem 75

Python by Althalus

Runtime: 22.14s

def gcd(a,b):
    while b != 0:
        tmp = a % b 
        a = b 
        b = tmp 
    return a

def get_triple():
    m,n = 1,1 
    while True:
        m += 1
        if m >= n:
            m = 1 
            n += 1
        if (gcd(m,n) == 1) and (m%2 == 0 or n%2 == 0): 
            a,b,c = (n*n)-(m*m),2*m*n,(m*m)+(n*n)
            yield a,b,c 

triples = get_triple()
ls = {}
a,b,c = triples.next()
target=1500000
for x in xrange(1500000):
    if a+b+c <= target:
        i = 1 
        a1,b1,c1 = a*i,b*i,c*i
        while a1+b1+c1 <= target:
            try:
                ls[a1+b1+c1]+=1
            except:
                ls[a1+b1+c1] = 1 
            i+=1
            a1,b1,c1 = a*i,b*i,c*i
    else:
        pass
    a,b,c = triples.next()

print sum ([x for x in ls.values() if x == 1])
Personal tools