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 


<?php
 
function gcd($a, $b)
{
    if ($a == 0)
       return $b;
    if ($b == 0)
       return $a;
    if($a == $b)
        return $a;
    if($a > $b)
        return gcd($a-$b, $b);
    return gcd($a, $b-$a);
}
 
$pytha = 0;
$prim = 0;
$max_p = 100;
 
for ($a = 1; $a <= $max_p / 3; $a++) {
    $aa = $a**2;
    for ($b = $a + 1; $b < $max_p/2; $b++) {
        $bb = $b**2;
        for ($c = $b + 1; $c < $max_p/2; $c++) {
            $cc = $c**2;
            if ($aa + $bb < $cc) break;
            if ($a + $b + $c > $max_p) break;
 
            if ($aa + $bb == $cc) {
                $pytha++;
                if (gcd($a, $b) == 1) $prim++;
            }
        }
    }
}
 
echo 'Up to ' . $max_p . ', there are ' . $pytha . ' triples, of which ' . $prim . ' are primitive.';