A short iterational algorithm for calculating the greatest common divisor using the Euclidean algorithm.
function gcd(a, b:Longword):Longword; var t:Longword; begin while b <> 0 do begin t := b; b := a mod b; a := t; end; gcd := a; end;
This function can be used for calculating Euler’s Totient function:
function fi(a:Longword):Longword; var i:Longword; count:Longword; begin if a = 1 then begin count := 1; Exit end; count := 0; for i := 1 to a do begin if gcd(i, a) = 1 then count := count +1; end; fi := count; end;
N.B. Keep in mind that this algorithms are far from optimal.