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
themast3r: 2017-06-17 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/segmented-sieve/ . You are enough equipped with knowledge know to tackle this problem.

shauryauppal: 2017-06-06 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.
As soon as I removed the caching part got AC.

USE->http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
calculator to verify your answer->http://www.javascripter.net/math/calculators/eulertotientfunction.htm

ode_to_code: 2017-05-31 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: 2017-05-25 13:46:53

TLE in java... any way to solve this in java?

v_ns: 2017-03-31 16:38:13

Take help from here:- https://www.topcoder.com/community/data-science/data-science-tutorials/prime-numbers-factorization-and-euler-function/

dinkar: 2017-03-26 09:03:28

Can anybody help me how to solve this problem using Java.
I have submitted same logic in c++ and submission is accepted but Java gives TLE.

Any suggestions to submit in Java ?

rohit9934: 2017-03-07 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++.

vladimira: 2017-02-22 02:29:03

0.06 secs with python! Hell yeah!

nilabja16180: 2017-02-19 11:35:33

AC in ONE GO!

scorpion_ajay: 2017-01-17 09:00:37

can be done using gcd, but use euler's product formula
topcoder <3
AC in a go, easy one :)


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