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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
0 Comments
If you have any doubts, Please let me know