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 


/*REXX program counts the number of  Pythagorean triples  that exist given a maximum    */
/*──────────────────── perimeter of  N, and also counts how many of them are primitives.*/
parse arg N .                                    /*obtain optional argument from the CL.*/
if N=='' | N==","  then N= 100                   /*Not specified?  Then use the default.*/
              do j=1  for N;   @.j= j*j;   end   /*pre-compute some squares.            */
N66= N * 2%3                                     /*calculate  2/3  of  N     (for a+b). */
T= 0;   P= 0                                     /*set the number of Triples, Primitives*/
              do a=3  to N%3                     /*limit  side  to 1/3 of the perimeter.*/
                 do b= a+1                       /*the triangle can't be  isosceles.    */
                 ab= a + b                       /*compute a partial perimeter (2 sides)*/
                 if ab>=N66       then iterate a /*is a+b≥66% perimeter? Try different A*/
                 aabb= @.a + @.b                 /*compute the sum of  a²+b²  (shortcut)*/
                    do c=b+1                     /*compute the value of the third side. */
                    if ab+c > N   then iterate a /*is a+b+c>perimeter ? Try different A.*/
                    if @.c >aabb  then iterate b /*is     c²  > a²+b² ? Try      "    B.*/
                    if @.c\==aabb then iterate   /*is     c² ¬= a²+b² ? Try      "    C.*/
                    T= T + 1                     /*eureka. We found a Pythagorean triple*/
                    P= P + (gcd(a, b)==1)        /*is this  triple  a primitive triple? */
                    end   /*c*/
                 end      /*b*/
              end         /*a*/
_= left('', 7)                                   /*for padding the output with 7 blanks.*/
say 'max perimeter ='    N   _    "Pythagorean triples ="    T    _    'primitives ='    P
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
gcd: procedure; parse arg x,y;  do until y==0; parse value x//y y with y x; end;  return x