ETF - Euler Totient Function

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

//{$APPTYPE CONSOLE}
 {$MODE DELPHI}

var
    f, t : array[1..1000000] of integer;
    i, j, n, st : integer;

begin
    f[1] := 1;
    for i:=1 to 1000000 do t[i] := i;
    for i:=2 to 1000000 do if t[i] = i then
    begin
        j := i + i;
        while j <= 1000000 do
        begin
            t[j] := i;
            j := j + i;
        end;
    end;
    for i:=2 to 1000000 do
    begin
        n := i;
        j := 1;
        while n mod t[i]=0 do
        begin
            n := n div t[i];
            j := j * t[i];
        end;
        f[i] := f[n] * (j - j div t[i]);
    end;
    read(st);
    while st > 0 do
    begin
        read(n);
        writeln(f[n]);
        dec(st);
    end;
end.

Download