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 


 
print time$()
 
for power =1 to 6
    perimeterLimit =10^power
    upperBound     =int( 1 +perimeterLimit^0.5)
    primitives     =0
    triples        =0
    extras         =0   '   will count the in-range multiples of any primitive
 
    for m =2 to upperBound
        for n =1 +( m mod 2 =1) to m -1 step 2
            term1      =2 *m *n
            term2      =m *m -n *n
            term3      =m *m +n *n
            perimeter  =term1 +term2 +term3
 
            if perimeter <=perimeterLimit then triples =triples +1
 
            a     =term1
            b     =term2
 
            do
                r = a mod b
                a =b
                b =r
            loop until r <=0
 
            if ( a =1) and ( perimeter <=perimeterLimit) then                       'we've found a primitive triple if a =1, since hcf =1. And it is inside perimeter range. Save it in an array
                primitives =primitives +1
                if term1 >term2 then temp =term1: term1 =term2: term2 =temp         'swap so in increasing order of side length
                nEx =int( perimeterLimit /perimeter)                     'We have the primitive & removed any multiples. Now calculate ALL the multiples in range.
                extras =extras +nEx
            end if
 
            scan
        next n
    next m
 
    print "  Number of primitives having perimeter below "; 10^power, " was "; primitives, " & "; extras, " non-primitive triples."
    print time$()
next power
 
print "End"
end
 