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:


#include<bits/stdc++.h>
using namespace std;
/// Typedef
typedef long long ll;
ll EularPHI(ll num)
{
double ans = num;
for(ll i = 2; i * i <= num; i++){
if(num % i == 0){
while (num % i == 0) {
num /= i;
}
ans *= (1.0 - (1.0 / (double)i));
}
}
if(num > 1) ans *= (1.0 - (1.0 / (double)num));
return (ll)ans;
}
int main()
{
ll tc, num, t = 1, pownum;
for(ll i = 1; i <= 10; i++){
if(i == 1){
cout << i << " Co-Prime Count : 0" << endl;
continue;
}
cout << i << " Co-Prime Count : " << EularPHI(i) << endl;
}
return 0;
}

Post a Comment

0 Comments