ETF - Euler Totient Function

In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 <= n <= 10^6). Compute the value of the totient φ.

Input

First line contains an integer T, the number of test cases. (T <= 20000)

T following lines, each contains an integer n.

Output

T lines, one for the result of each test case.

Example

```Input:
5
1
2
3
4
5

Output:
1
1
2
2
4```

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define MOD (ll)1000000007
#define pb 	push_back
#define EPS 1e-9
#define FOR(i, n)	for(int i = 0;i < n; i++)
#define pi(a)   printf("%d\n", a)
#define all(c)  c.begin(), c.end()
#define tr(container, it)   for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}

const int MAXN = 1e6+5;
int minPrime[MAXN];
void sieve(){
minPrime[1] = 1;
for(int i = 2; i*i <= MAXN; i++){
if(minPrime[i] == 0){
if(i*(ll)1*i <= MAXN){
for(int j = i*i; j <= MAXN; j += (i)){
if(minPrime[j] == 0)
minPrime[j] = i;
}
}
}
}
for(int i = 2;i <= MAXN; i++){
if(minPrime[i] == 0)
minPrime[i] = i;
}
}
/* Time Complexity - O(logN + nloglogN> */
vector<int> factors;
ll eulerPhi(int n){
set<int> s;
ll res = n;
while(n!=1){
if(s.empty() || s.find(minPrime[n]) == s.end()){
res = res-res/minPrime[n];
s.insert(minPrime[n]);
}
n/=minPrime[n];
}
return res;
}

int main(int argc, char const *argv[]){
int t;
si(t);
sieve();
while(t--){
int n;
si(n);
printf("%lld\n", eulerPhi(n));
}
return 0;
}``````
Copy The Code &

Input

cmd
5
1
2
3
4
5

Output

cmd
1
1
2
2
4

#2 Code Example with Java Programming

```Code - Java Programming```

``````import java.lang.StringBuilder;
import java.io.DataInputStream;
import java.io.IOException;

final private int BUFFER_SIZE = 1 << 16;
private DataInputStream dis;
private byte[] buffer;

dis = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

public void omitLines(int n) throws IOException{
while (n > 0){
n--;
}
}

public int nextInt() throws IOException{
int ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do{
ret = ret * 10 + c - '0';
}  while ((c = read()) >= '0' && c <= '9');

if (neg)
return -ret;
return ret;
}

public long nextPositiveLong() throws IOException{
long ret = 0;
while (c <= ' ')
do{
ret = ret * 10 + c - '0';
}  while ((c = read()) >= '0' && c <= '9');

return ret;
}

public int nextPositiveInt() throws IOException{
int ret = 0;
while (c <= ' ')
do{
ret = ret * 10 + c - '0';
}  while ((c = read()) >= '0' && c <= '9');

return ret;
}

private void fillBuffer() throws IOException{
buffer[0] = -1;
}

fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException{
if (dis == null)
return;
dis.close();
}
}

final class ETF{
final static int [] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};

public static int phi(int n){
int result = n;

for (int p : primes){
if (p*p > n) break;
if (n % p == 0){
result -= result/p;

n /= p;
while (n % p == 0){
n /= p;
}
}
}

if (n > 1){
result -= result/n;
}

return result;
}

public static void main(String args[]) throws IOException{
StringBuilder sb = new StringBuilder();
int T = r.nextPositiveInt(), n;

while (T-- > 0){
n = r.nextPositiveInt();

sb.append(phi(n));
sb.append('\n');
}
System.out.print(sb.toString());
}
}``````
Copy The Code &

Input

cmd
5
1
2
3
4
5

Output

cmd
1
1
2
2
4