Spoj ETF Solution

#include<bits/stdc++.h>

#define N 1000002

using namespace std;

int p[N+5];

int phi[N+5];

void prime()

{

p[0] = p[1] = 1;

for(int i=2; i*i<=N; i++)

{

if(p[i] == 0)

{

for(int j=2; i*j<=N; j++)

p[i*j] = 1;

}

}

}

void phifucntion()

{

for(int i=1; i<=N; i++)

phi[i] = i;

for(int i=2; i<=N; i++)

{

if(p[i] == 0)

{

for(int j=i; j<=N; j+=i)

phi[j] = phi[j] / i* (i-1);

}

}

}

int main()

{

prime();

phifucntion();

int t;

cin >> t;

while(t--)

{

int n;

cin >> n;

cout << phi[n] << "\n";

}

return 0;

}