Pythagorean triples: Difference between revisions

=={{header|OCaml}}==

<lang OCaml>let isqrt n =

let rec iter t =

let d = n - t*t in

if (0 <= d) && (d < t+t+1) (* t*t <= n < (t+1)*(t+1) *)

then t else iter ((t+(n/t))/2) in iter 1

let rec gcd a b =

let t = a mod b in

if t = 0 then b else gcd b t

let coprime a b = gcd a b = 1

let num_to ms =

let ctr = ref 0 in

let prim_ctr = ref 0 in

let max_m = isqrt (ms/2) in

for m = 2 to max_m do

for j = 0 to (m/2) - 1 do

let n = m-(2*j+1) in

if coprime m n then

let s = 2*m*(m+n) in

if s <= ms then

(ctr := !ctr + (ms/s); incr prim_ctr)

done

done; (!ctr, !prim_ctr)

let show i =

let s, p = num_to i in

Printf.printf "For perimeters up to %d there are %d total and %d primitive\n%!" i s p;;

List.iter show [ 100; 1000; 10000; 100000; 1000000; 10000000; 100000000 ]</lang>

Output:

<pre>For perimeters up to 100 there are 17 total and 7 primitive

For perimeters up to 1000 there are 325 total and 70 primitive

For perimeters up to 10000 there are 4858 total and 703 primitive

For perimeters up to 100000 there are 64741 total and 7026 primitive

For perimeters up to 1000000 there are 808950 total and 70229 primitive

For perimeters up to 10000000 there are 9706567 total and 702309 primitive

For perimeters up to 100000000 there are 113236940 total and 7023027 primitive</pre>