A Pythagorean triple is defined as three positive integers 



(
a
,
b
,
c
)


{\displaystyle (a,b,c)}

 where 



a
<
b
<
c


{\displaystyle a<b<c}

, and 




a

2


+

b

2


=

c

2


.


{\displaystyle a^{2}+b^{2}=c^{2}.}



They are called primitive triples if 



a
,
b
,
c


{\displaystyle a,b,c}

 are co-prime, that is, if their pairwise greatest common divisors 





g
c
d


(
a
,
b
)
=


g
c
d


(
a
,
c
)
=


g
c
d


(
b
,
c
)
=
1


{\displaystyle {\rm {gcd}}(a,b)={\rm {gcd}}(a,c)={\rm {gcd}}(b,c)=1}

.

Because of their relationship through the Pythagorean theorem, a, b, and c are co-prime if a and b are co-prime (





g
c
d


(
a
,
b
)
=
1


{\displaystyle {\rm {gcd}}(a,b)=1}

).  

Each triple forms the length of the sides of a right triangle, whose perimeter is 



P
=
a
+
b
+
c


{\displaystyle P=a+b+c}

.



Task

The task is to determine how many Pythagorean triples there are with a perimeter no larger than 100 and the number of these that are primitive.



Extra credit
 
Deal with large values.   Can your program handle a maximum perimeter of 1,000,000?   What about 10,000,000?   100,000,000?

Note: the extra credit is not for you to demonstrate how fast your language is compared to others;   you need a proper algorithm to solve them in a timely manner.



Related tasks

   Euler's sum of powers conjecture 
   List comprehensions
   Pythagorean quadruples 


import math
 
// a function to check if three numbers are a valid triple
def is_triple(a, b, c)
    if not (a < b) and (b < c)
        return false
    end
 
    return (a^2 + b^2) = c^2
end
 
// a function to check if the numbers are coprime
def is_coprime(a, b, c)
    global math
    return (math.gcd(a, b)=1) && (math.gcd(a, c)=1) && (math.gcd(b, c)=1)
end
 
// the maximum perimeter to check
perimeter  = 100
perimeter2 = int(perimeter / 2) - 1
perimeter3 = int(perimeter / 3) - 1
 
// loop though and look for pythagorean triples
ts = 0
ps = 0
for a in range(1, perimeter3)
    for b in range(a + 1, perimeter2)
        for c in range(b + 1, perimeter2)
            if (a + b + c) <= perimeter
                if is_triple(a,b,c)
                    ts += 1
                    print a + ", " + b + ", " + c
                    if is_coprime(a,b,c)
                        ps += 1
                        print " primitive"
                    end
                    println
                end
            end
        end
    end
end
 
print   "Up to a perimeter of " + perimeter + ", there are " + ts
println " triples, of which " + ps + " are primitive."