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
jayharsh:
20170812 14:59:14
AC in One Go ! 0.03 Sec........ 

dangerous321:
20170704 09:19:14
AC in one go in C


mehul_sri:
20170629 12:19:29
I don't know why but using int gave me wa. Use long long int.


themast3r:
20170617 23:24:47
Those who need help, first read this : https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_product_formula and then this : http://www.geeksforgeeks.org/segmentedsieve/ . You are enough equipped with knowledge know to tackle this problem. 

shauryauppal:
20170606 00:10:24
Space Complexity also very limited,I was caching my answer once calculated with (array / map tried both) but I got wrong answer all the time.


ode_to_code:
20170531 09:45:25
can anyone post a link for the most efficient fast i/o code in java . i have tried ones given on geek for geeks and hacker earth but still get tle. have faced the same problem in many questions. please its a humble request on behalf of all java noobs . 

hk_visact:
20170525 13:46:53
TLE in java... any way to solve this in java? 

v_ns:
20170331 16:38:13
Take help from here: https://www.topcoder.com/community/datascience/datasciencetutorials/primenumbersfactorizationandeulerfunction/ 

dinkar:
20170326 09:03:28
Can anybody help me how to solve this problem using Java.


rohit9934:
20170307 18:38:23
See Wikipedia Article for Euler Totient Function and Try to develop your own code,If you again stuck, check out the Topcoder Tutorial for the same. 0.07 sec with c++. 
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 