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 


def gcd(a; b):
  def _gcd:
    if .[1] == 0 then .[0]
    else [.[1], .[0] % .[1]] | _gcd
    end;
  [a,b] | _gcd ;
 
# Return: [total, primitives] for pythagorean triangles having
# perimeter no larger than peri.
# The following uses Euclid's formula with the convention: m > n.
def count(peri):
 
  # The inner function can be used to count for a given value of m:
  def _count:
    # state [n,m,p, [total, primitives]]
    .[0] as $n | .[1] as $m | .[2] as $p
    | if $n < $m and $p <= peri then
        if (gcd($m;$n) == 1)
        then .[3] | [ (.[0] + ((peri/$p)|floor) ),  (.[1] + 1)]
        else .[3]
        end
        | [$n+2, $m, $p+4*$m, .] | _count
      else .
      end;
 
  # m^2 < m*(m+1) <= m*(m+n) = perimeter/2
  reduce range(2;  (peri/2) | sqrt + 1) as $m
    ( [1, 2, 12, [0,0]];
      (($m % 2) + 1) as $n
      | (2 * $m * ($m + $n) ) as $p   # a+b+c for this (m,n)
      | [$n, $m, $p, .[3]] | _count
    ) | .[3] ;
 
# '''Example''':
def pow(i): . as $in | reduce range(0; i) as $j (1; . * $in);
 
range(1; 9) | . as $i | 10|pow($i) as $i | "\($i):  \(count($i) )"
 