PROBLEM LINK:
Author: Akash Kumar Bhagat
Tester: Soham Chakrabarti
Editorialist: Akash Kumar Bhagat
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Prime Factors , Totient Function
EXPLANATION:
According to the question, one has to print the total number of Co-primes related to N less than N itself. In other words, one has to print the Totient Function Value of the number N. One can compute the Totient Function in various ways an article on GeeksForGeeks. One of the ways of finding the totient value is shown here.
According to Mathworld.com
\phi(N) = \prod_{p}(1-1/p)
Here, \phi(N) is the Totient Function
& P is the distinct prime factors of N
One can easily find the prime factors (O(sqrt(n))) and put it in the above equation to get the desired answer.
Do share your approach to the problem 