The Ada Program: euler_phi.adb

  1 -- euler_phi.adb: compute Euler's phi function, number of relatively prime
  2 
  3 -- phi(n) is the number of positive integers m such that
  4 --   1<=m<n and gcd(m,n)=1
  5 
  6 function Euler_Phi (N: Positive) return Positive is
  7    Remainder, Phi : Positive := N;
  8    Odd : Positive;
  9 begin
 10    if Remainder mod 2 = 0 then
 11       Phi := Phi / 2;
 12       while Remainder mod 2 =0 loop Remainder := Remainder / 2; end loop;
 13    end if;
 14    Odd := 3;
 15    while Odd <= Remainder loop
 16       if Remainder mod Odd = 0 then
 17          -- "Odd" must be prime factor of Remainder
 18          Phi := Phi * (Odd - 1) / Odd;
 19          while Remainder mod Odd = 0 loop Remainder := Remainder / Odd; end loop;
 20       end if;
 21       Odd := Odd + 2;
 22    end loop;
 23    return (Phi);
 24 end Euler_Phi;