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
|
kkunal_1:
2020-10-26 12:28:51
AC in one go ,first time
|
|
prajjwal1999:
2020-09-19 13:26:54
GOOD QUESTION
|
|
paxton:
2020-09-01 16:52:41
@abhisek_1357, read this https://cp-algorithms.com/algebra/phi-function.html |
|
kishor_e:
2020-08-11 09:40:37
read this topic
|
|
auler_:
2020-07-15 15:52:51
@abhisek_1357, you need to divide it before multiplying. otherwise you will have integer overflow. |
|
abhisek_1357:
2020-07-06 17:54:32
Can someone please share his/her approach ...and also if possible please debugg mine...
|
|
kumar_anubhav:
2020-06-19 15:17:08
AC in one GO !! :)
|
|
coolboy7:
2020-06-09 19:53:10
nice question |
Added by: | Race with time |
Date: | 2009-03-27 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |