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 


DEFINE PTR="CARD"
DEFINE ENTRY_SIZE="3"
TYPE TRIPLE=[BYTE a,b,c]
TYPE TRIPLES=[
  PTR buf ;BYTE ARRAY
  BYTE count]
 
PTR FUNC GetItemAddr(TRIPLES POINTER arr BYTE index)
  PTR addr
 
  addr=arr.buf+index*ENTRY_SIZE
RETURN (addr)
 
PROC PrintTriples(TRIPLES POINTER arr)
  INT i
  TRIPLE POINTER t
 
  FOR i=0 TO arr.count-1
  DO
    t=GetItemAddr(arr,i)
    PrintF("(%B %B %B) ",t.a,t.b,t.c)
  OD 
RETURN
 
PROC Init(TRIPLES POINTER arr BYTE ARRAY b)
  arr.buf=b
  arr.count=0
RETURN
 
PROC AddItem(TRIPLES POINTER arr TRIPLE POINTER t)
  TRIPLE POINTER p
 
  p=GetItemAddr(arr,arr.count)
  p.a=t.a
  p.b=t.b
  p.c=t.c
  arr.count==+1
RETURN
 
PROC FindTriples(TRIPLES POINTER res BYTE limit)
  BYTE ARRAY data(100)
  BYTE half,i,j,k
  TRIPLE t
 
  Init(res,data)
  half=limit/2
  FOR i=1 TO half
  DO
    FOR j=i TO half
    DO
      FOR k=j TO limit
      DO
        IF i+j+k<limit AND i*i+j*j=k*k THEN
          t.a=i t.b=j t.c=k
          AddItem(res,t)
        FI
      OD
    OD
  OD
RETURN
 
BYTE FUNC Gcd(BYTE a,b)
  BYTE tmp
 
  IF a<b THEN
    tmp=a a=b b=tmp
  FI
 
  WHILE b#0
  DO
    tmp=a MOD b
    a=b b=tmp
  OD
RETURN (a)
 
BYTE FUNC IsPrimitive(TRIPLE POINTER t)
  IF Gcd(t.a,t.b)>1 THEN RETURN (0) FI
  IF Gcd(t.b,t.c)>1 THEN RETURN (0) FI
  IF Gcd(t.a,t.c)>1 THEN RETURN (0) FI
RETURN (1)
 
PROC FindPrimitives(TRIPLES POINTER arr,res)
  BYTE ARRAY data(100)
  INT i
  TRIPLE POINTER t
 
  Init(res,data)
  FOR i=0 TO arr.count-1
  DO
    t=GetItemAddr(arr,i)
    IF IsPrimitive(t) THEN
      AddItem(res,t)
    FI
  OD
RETURN
 
PROC Main()
  DEFINE LIMIT="100"
  TRIPLES res,res2
 
  FindTriples(res,LIMIT)
  PrintF("There are %B pythagorean triples with a perimeter less than %B:%E%E",res.count,LIMIT)
  PrintTriples(res)
 
  FindPrimitives(res,res2)
  PrintF("%E%E%E%B of them are primitive:%E%E",res2.count)
  PrintTriples(res2)
RETURN