Tutorials  Articles  Notifications  Login  Signup


ETF - Euler Totient Function

Problem statement
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 format
First line contains an integer T, the number of test cases. T following lines, each contains an integer n.

Output format
T lines, one for the result of each test case.

Constraints
The number of test cases. (T <= 20000)

Sample Input 1
5
1
2
3
4
5


Sample output 1
1
1
2
2
4



Explanation
N/A





// Write your code here in C++


Editiorial

https://en.wikipedia.org/wiki/Euler%27s_totient_function http://mathworld.wolfram.com/TotientFunction.html https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function https://oeis.org/A000010



go back Go back to Mathematics



Author: Rajan Shah

Level: Medium

Uploaded on: Dec. 1, 2019

Lab: Mathematics

Section: None


Found something wrong ? Inform us



Other problems from this lab

Small Factorials

Subarray with given sum

Maximum Index

Finding the numbers