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
|
dennislo:
2018-06-13 05:48:33
For Java: compute + memoize totient values as you are creating the prime sieve |
|
s_a_k_s_h_a_m:
2018-06-11 09:43:24
ans*=(1-1.0/i) will give you WA
|
|
aadichai22:
2018-06-02 16:04:36
Ac in one go..!
|
|
prakharvk:
2018-05-22 13:29:43
Very basic question, can be done with basic knowledge of totient function. |
|
ramini1996:
2018-02-06 14:06:22
Use long long !!! |
|
vishesh_345:
2017-12-28 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:
2017-12-11 18:33:43
ac in one go:) |
|
Ravi Upadhyay:
2017-11-20 10:07:00
if you are using euler totient formula then make sure to divide by p before multiplying by p-1, or else use long long int to avoid overflow. |
|
ameyanator:
2017-11-18 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:
2017-08-12 14:59:14
AC in One Go ! 0.03 Sec........ |
| 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