Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include<iostream>
#include<algorithm>
#include<cstdio>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define maxn 1000000
using namespace std;

int f[maxn+10];

void etf()
{
   int i,j;
   fr(i,1,maxn) f[i]=i/(i%2?1:2);
   fr(i,3,maxn)
     if (f[i]==i)
       for (int j=i;j<=maxn;j+=i)
         f[j]=f[j]/i*(i-1);
}

int main()
{
   etf();
   int test,n;
   cin >> test;
   while (test--) scanf("%d",&n), printf("%d\n",f[n]);
   return 0;
}

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
using namespace std;

#define N 1000000
int f[N+1];
bool prime[N+1];

void eratos() {
    memset(prime, -1, sizeof prime);
    prime[0] = prime[1] = 0;
    for(int i = 2; i * i <= N; ++i) if(prime[i])
        for(int j = i+i; j <= N; j += i) prime[j] = 0;
}

void calcF() {
    for(int i = 1; i <= N; ++i) f[i] = i;
    for(int i = 2; i <= N; ++i) if(prime[i])
        for(int j = i; j <= N; j += i) f[j] = f[j] / i * (i-1);
}

int main() {
    eratos();
    calcF();
    int tc; scanf("%d", &tc);
    while(tc--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", f[n]);
    }
    return 0;
}

Code mẫu của ladpro98

#include <iostream>

using namespace std;

const int N = 1000006;

int phi[N], np[N], prime[N];
int nPrime;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    for (int i = 2; i < N; ++i) {
        if (!np[i]) prime[nPrime++] = np[i] = i;
        for (int j = 0; j < nPrime && prime[j] <= np[i] && prime[j] * i < N; ++j)
            np[prime[j] * i] = prime[j];
    }
    phi[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (np[i] == i) {
            phi[i] = i - 1;
            continue;
        }
        int j = i / np[i];
        if (j % np[i])
            phi[i] = phi[j] * phi[np[i]];
        else
            phi[i] = phi[j] * np[i];
    }
    int nTest; cin >> nTest;
    while (nTest--) {
        int n; cin >> n;
        cout << phi[n] << '\n';
    }
    return 0;
}

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       1000001;
var
  f1,f2         :       text;
  phi           :       array[1..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure init;
    var
      i,j:longint;
    begin
      for i:=1 to MAXN do phi[i]:=i;
      for i:=2 to MAXN do
      if phi[i]=i then //i la so nguyen to
        begin
          j:=i;
          while j<=MAXN do
            begin
              phi[j]:=phi[j] div i*(i-1);
              j+=i;
            end;
        end;
    end;
function cal(n:longint):int64;
    var
      sum:int64;
    begin
    end;
procedure solve;
    var
      test,n:longint;
    begin
      read(f1,test);
      for test:=1 to test do
        begin
          read(f1,n);
          writeln(f2,phi[n]);
        end;
    end;

begin
  openF;
  init;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
main()
 {
 long n[200],t=2,T,N;
 n[1]=2;
 n[2]=3;
 for(long i=4;i<1100;i++)
   {
   int k=0;        
   for(long j=1;j<=t;j++)
     {
     if(i%n[j]==0)
       {
       k=1;
       break;
       }
     else if(n[j]>sqrt(i))     
       break;
     }
   if(k==0)
     {
     t++;
     n[t]=i;
     }        
   }              
 scanf("%ld",&T);
 for(int i=1;i<=T;i++)
    {     
    scanf("%ld",&N);
    long k=1,KQ=1;                  
    for(long i=1;i<=180;i++)
      {
      if(N==1)
        break;       
      else if(n[i]>sqrt(N))
          {
          KQ*=(N-1);              
          break;
          }     
      else if(N%n[i]==0)
          {
          long t=0;                
          do
            {
            N=N/n[i];
            t++;
            }while(N%n[i]==0);
          KQ=KQ*(n[i]-1)*pow(n[i],t-1);
          }                      
      }                                             
    printf("%ld\n",KQ);
    }
 //getch();
 }

Code mẫu của ll931110

Program ETF;
  Const
    input  = '';
    output = '';
    maxn = 1000000;
  Var
    a,F: array[1..maxn] of longint;
    t,n,i: longint;
    fi,fo: text;

Procedure openfile;
  Begin
    Assign(fi, input);
      Reset(fi);

    Assign(fo, output);
      Rewrite(fo);
  End;

Procedure solve;
  Var
    i,j,k,tmp: longint;
  Begin
    Fillchar(a, sizeof(a), 0);
    For i:= 2 to trunc(sqrt(maxn)) do
      if a[i] = 0 then
      Begin
        k:= 2 * i;
        While k <= maxn do
          Begin
            a[k]:= i;
            k:= k + i;
          End;
      End;

    F[1]:= 1;
    For i:= 2 to maxn do
      if a[i] = 0 then F[i]:= i - 1 else
        Begin
          k:= 0;
          tmp:= i;

          While tmp mod a[i] = 0 do
            Begin
               inc(k);
               tmp:= tmp div a[i];
            End;

          If tmp = 1 then
            Begin
              F[i]:= a[i] - 1;
              For j:= 1 to k - 1 do F[i]:= F[i] * a[i];
            End
          else F[i]:= F[tmp] * F[i div tmp];
        End;
  End;

Procedure closefile;
  Begin
    Close(fo);
    Close(fi);
  End;

Begin
  openfile;
  solve;

  Readln(fi, t);
  For i:= 1 to t do
    Begin
      Readln(fi, n);
      Writeln(fo, F[n]);
    End;

  closefile;
End.

Code mẫu của khuc_tuan

//{$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.