AquilaX’s development blog

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.