# 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