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
|
anant6025:
2019-02-06 21:06:14
Easy question if you know Sieve,Prime factorisation
|
|
daku5768:
2019-01-07 16:20:49
my 50th finally |
|
gokul27:
2018-12-26 10:58:14
AC in one go!
|
|
raghav6:
2018-12-24 10:41:54
Finally AC with the sieve of Eratosthenes! |
|
yaseenmollik:
2018-12-15 02:08:30
AC in one go using prime factorization |
|
sea_26:
2018-11-21 09:31:42
Accepted in one go!
|
|
aj_254:
2018-10-09 19:47:08
how to get rid of tle in python 3.i m using o(sqrt(n)) algorithim
|
|
bendal:
2018-08-09 16:15:50
how do i overcome TLe in c++,i'm using inbuild gcd function. |
|
deceptiveuser1:
2018-08-02 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:
2018-06-20 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 |
| Added by: | Race with time |
| Date: | 2009-03-27 |
| Time limit: | 0.161s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
RSS