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 


' version 30-05-2016
' compile with: fbc -s console
 
' primitive pythagoras triples
' a = m^2 - n^2, b = 2mn, c = m^2 + n^2
' m, n are positive integers and m > n
' m - n = odd and GCD(m, n) = 1
' p = a + b + c
 
' max m for give perimeter
' p = m^2 - n^2 + 2mn + m^2 + n^2
' p = 2mn + m^2 + m^2 + n^2 - n^2 = 2mn + 2m^2
' m >> n and n = 1 ==> p = 2m + 2m^2 = 2m(1 + m)
' m >> 1 ==> p = 2m(m) = 2m^2
' max m for given perimeter = sqr(p / 2)
 
Function gcd(x As UInteger, y As UInteger) As UInteger
 
    Dim As UInteger t
 
    While y
        t = y
        y = x Mod y
        x = t
    Wend
    Return x
 
End Function
 
 
Sub pyth_trip(limit As ULongInt, ByRef trip As ULongInt, ByRef prim As ULongInt)
 
    Dim As ULongInt perimeter, lby2 = limit Shr 1
    Dim As UInteger m, n
    Dim As ULongInt a, b, c
 
    For m = 2 To Sqr(limit / 2)
        For n = 1 + (m And 1) To (m - 1) Step 2
            ' common divisor, try next n
            If (gcd(m, n) > 1) Then Continue For
            a = CULngInt(m) * m - n * n
            b = CULngInt(m) * n * 2
            c = CULngInt(m) * m + n * n
            perimeter = a + b + c
            ' perimeter > limit, since n goes up try next m
            If perimeter >= limit Then Continue For, For
            prim += 1
            If perimeter < lby2 Then
                trip += limit \ perimeter
            Else
                trip += 1
            End If
        Next n
    Next m
 
End Sub
 
 
' ------=< MAIN >=------
 
Dim As String str1, buffer = Space(14)
Dim As ULongInt limit, trip, prim
Dim As Double t, t1 = Timer
 
Print "below           triples   primitive            time"
Print
 
For x As UInteger = 1 To 12
    t = Timer
    limit = 10 ^ x : trip = 0 : prim = 0
    pyth_trip(limit, trip, prim)
    LSet buffer, Str(prim) : str1 = buffer
    Print Using "10^##  ################   "; x; trip;
    If x > 7 Then
        Print str1;
        Print Using "  ######.## sec."; Timer - t
    Else
        Print str1
    End If
Next x
 
Print : Print
Print Using "Total time needed #######.## sec."; Timer - t1
 
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End