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
hide comments
aj_254:
20181009 19:47:08
how to get rid of tle in python 3.i m using o(sqrt(n)) algorithim


bendal:
20180809 16:15:50
how do i overcome TLe in c++,i'm using inbuild gcd function. 

deceptiveuser1:
20180802 21:35:30
i have cross checked my answers a lot of times, still getting wrong answer, can the problem setter please check my solution out 22086785 

ada107:
20180620 15:16:46
I am getting tle in java but got it correct in c++, can anyone tell how to improve in java, have used fast scanner and printer but then also getting tle 

dennislo:
20180613 05:48:33
For Java: compute + memoize totient values as you are creating the prime sieve 

s_a_k_s_h_a_m:
20180611 09:43:24
ans*=(11.0/i) will give you WA


aadichai22:
20180602 16:04:36
Ac in one go..!


prakharvk:
20180522 13:29:43
Very basic question, can be done with basic knowledge of totient function. 

ramini1996:
20180206 14:06:22
Use long long !!! 

vishesh_345:
20171228 12:00:34
It is better to find smallest prime factor and then rest of distinct factors compared to precomputing all the distinct prime factors. Second one would result into TLE. 
Added by:  Race with time 
Date:  20090327 
Time limit:  0.161s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 