Euler’s Totient Function find all CO-Prime count in a number

Euler’s Totient function for an input n is the count of numbers in {1, 2, 3, …, n} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1.

The above code calls gcd function O(n) times. The time complexity of the gcd function is O(h) where h is the number of digits in a smaller number of given two numbers. Therefore, an upper bound on time complexity of the above solution is O(nLogn) [How? there can be at most Log10n digits in all numbers from 1 to n]

Below is a Better Solution. The idea is based on Euler’s product formula which states that the value of totient functions is below product over all prime factors p of n.

Euler product:

The formula basically says that the value of is equal to n multiplied by the product of (1 – 1/p) for all prime factors p of n. For example value of ?(6) = 6 * (1-1/2) * (1 – 1/3) = 2.



Algorithms:

1) Initialize : result = n
2) Run a loop from 'p' = 2 to sqrt(n), do following for every 'p'.
     a) If p divides n, then
           Set: result = result  * (1.0 - (1.0 / (float) p));
           Divide all occurrences of p in n.
3) Return result

references

Code: