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
ihg_26:
20180317 20:24:41
@themas3r http://www.geeksforgeeks.org/segmentedsieve/  this is giving tle in cpp


c_jain:
20180307 21:34:15
if facing difficulty then maybe this helps :)


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. 

spandana09:
20171211 18:33:43
ac in one go:) 

Ravi Upadhyay:
20171120 10:07:00
if you are using euler totient formula then make sure to divide by p before multiplying by p1, or else use long long int to avoid overflow. 

ameyanator:
20171118 21:00:12
AC with 0.01 secs in C++ using fast i/o. Time Complexity of my solution is T*sqrt(N). Fun problem but would need to read a bit on the totient function and some knowledge of how to work with prime numbers :) 

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.

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 