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 


PROGRAM PIT
 
BEGIN
 
  PRINT(CHR$(12);) !CLS
  PRINT(TIME$)
 
  FOR POWER=1 TO 7 DO
    PLIMIT=10#^POWER
    UPPERBOUND=INT(1+PLIMIT^0.5)
    PRIMITIVES=0
    TRIPLES=0
    EXTRAS=0          ! will count the in-range multiples of any primitive
 
    FOR M=2 TO UPPERBOUND DO
        FOR N=1+(M MOD 2=1) TO M-1 STEP 2 DO
            TERM1=2*M*N
            TERM2=M*M-N*N
            TERM3=M*M+N*N
            PERIMETER=TERM1+TERM2+TERM3
 
            IF PERIMETER<=PLIMIT THEN TRIPLES=TRIPLES+1
 
            A=TERM1
            B=TERM2
 
            REPEAT
                R=A-B*INT(A/B)
                A=B
                B=R
            UNTIL R<=0
 
            ! we've found a primitive triple if a = 1, since hcf =1.
            ! and it is inside perimeter range. Save it in an array
            IF (A=1) AND (PERIMETER<=PLIMIT) THEN
                PRIMITIVES=PRIMITIVES+1
 
                !-----------------------------------------------
                !swap so in increasing order of side length
                !-----------------------------------------------
                IF TERM1>TERM2 THEN SWAP(TERM1,TERM2)
                !-----------------------------------------------
                !we have the primitive & removed any multiples.
                !Now calculate ALL the multiples in range.
                !-----------------------------------------------
                NEX=INT(PLIMIT/PERIMETER)
                EXTRAS=EXTRAS+NEX
            END IF
 
            !scan
        END FOR
    END FOR
 
    PRINT("Primit. with perimeter <=";10#^power;"is";primitives;"&";extras;"non-prim.triples.")
    PRINT(TIME$)
  END FOR
 
  PRINT PRINT("** End **")
END PROGRAM