Introduction:
Euler’s totient function counts the total numbers between 1 to N, which are coprime to ‘N’. Two numbers are said to be coprime if the G.C.D.(Greatest Common Divisor) of both the numbers is 1.
1 is coprime to all the numbers.
Euler’s Totient function is also known as phifunction ϕ(N).
N  1  2  3  4  5  6  7  8  9  10  11  12  13  14 
ϕ(N)  1  1  2  2  4  2  6  4  6  4  10  4  12  6 
The above table shows the ϕ(N) value for the first few N values.
Let us see a few properties of the Euler’s Totient Function:

If a number(let us say ‘p’) is prime then gcd of ‘p’ with any number less than ‘p’ i.e. 1 <= q < p is equal to 1.
gcd(p, q) = 1
Hence, ϕ(p) = p  1. 
If ‘p’ is a prime number, then there are exactly p^{k }/ p numbers between 1 and p^{k} that are divisible by p.
Hence, ϕ(p^{k}) = p^{k}  p^{k  1}. 
If ‘a’ and ‘b’ are relatively prime then ϕ(ab) = ϕ(a) * ϕ(b).
This relation is derived from the Chinese remainder theorem.
Approach 1:
We can calculate the value of ϕ(N) using the above points by factorizing ‘N’.
Let us say N = (p_{1}^{a1}) * (p_{2}^{a2}) * (p_{3}^{a3}) * (p_{4}^{a4})...........* (p_{5}^{a5}) where p_{i }is a prime factor of ‘N’.
> ϕ(N) = ϕ(p_{1}^{a1}) * ϕ(p_{2}^{a2}) * ϕ(p_{3}^{a3}) * ϕ(p_{4}^{a4})...........* ϕ(p_{k}^{ak})
> = (p_{1}^{a1 } p_{1}^{a11}) * (p_{2}^{a2 } p_{1}^{a21}) * (p_{3}^{a3 } p_{1}^{a31})...........* (p_{k}^{ak } p_{k}^{ak1})
> = p_{1}^{a1} * (1  1/p_{1}) * p_{2}^{a2} * (1  1/p_{2}) * p_{3}^{a3} * (1  1/p_{3}).......* p_{k}^{ak} * (1  1/p_{k})
> = N * (1  1/p_{1}) * (1  1/p_{2}) * (1  1/p_{3}).......* (1  1/p_{k})
Let us implement the above approach:
#include<bits/stdc++.h> using namespace std; int eulerTotient(int n) { int ans = n; //Iterating till the sqaure root of 'n' for (int i = 2; i * i <= n; i++) { //If 'i' is a factor of 'n' if (n % i == 0) { while (n % i == 0){ n /= i; } ans = ans / i; } } if (n > 1){ ans = ans / n; } return ans; } int main() { int n = 12; cout << eulerTotient(n) << endl; } 
Output:
Time Complexity: The time complexity of the above approach is O(√N) because we are running an O(√N) for loop only.
Space Complexity: The space complexity for the above approach is O(1) because we are using constant auxiliary space.
Also see, Euclid GCD Algorithm