Table of contents

Introduction:

Approach 1:

Approach 2:

Approach 3:

FAQs:

Key Takeaways:

Last Updated: Mar 27, 2024

Euler’s Totient Function

Author Nishant Rana

Introduction:

Euler’s totient function counts the total numbers between 1 to N, which are coprime to ‘N’. Two numbers are said to be coprime if the G.C.D.(Greatest Common Divisor) of both the numbers is 1.

1 is coprime to all the numbers.

Euler’s Totient function is also known as phi-function ϕ(N).

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14
ϕ(N)	1	1	2	2	4	2	6	4	6	4	10	4	12	6

The above table shows the ϕ(N) value for the first few N values.

Let us see a few properties of the Euler’s Totient Function:-

If a number(let us say ‘p’) is prime then gcd of ‘p’ with any number less than ‘p’ i.e. 1 <= q < p is equal to 1.
gcd(p, q) = 1
Hence, ϕ(p) = p - 1.
If ‘p’ is a prime number, then there are exactly p^k/ p numbers between 1 and p^k that are divisible by p.
Hence, ϕ(p^k) = p^k - p^{k - 1}.
If ‘a’ and ‘b’ are relatively prime then ϕ(ab) = ϕ(a) * ϕ(b).
This relation is derived from the Chinese remainder theorem.

Approach 1:

We can calculate the value of ϕ(N) using the above points by factorizing ‘N’.

Let us say N = (p₁^a1) * (p₂^a2) * (p₃^a3) * (p₄^a4)...........* (p₅^a5) where p_iis a prime factor of ‘N’.

-> ϕ(N) = ϕ(p₁^a1) * ϕ(p₂^a2) * ϕ(p₃^a3) * ϕ(p₄^a4)...........* ϕ(p_k^ak)

-> = (p₁^a1- p₁^a1-1) * (p₂^a2- p₁^a2-1) * (p₃^a3- p₁^a3-1)...........* (p_k^ak- p_k^ak-1)

-> = p₁^a1 * (1 - 1/p₁) * p₂^a2 * (1 - 1/p₂) * p₃^a3 * (1 - 1/p₃).......* p_k^ak * (1 - 1/p_k)

-> = N * (1 - 1/p₁) * (1 - 1/p₂) * (1 - 1/p₃).......* (1 - 1/p_k)

Let us implement the above approach:

#include<bits/stdc++.h>
using namespace std;

int eulerTotient(int n) {
  int ans = n;

  //Iterating till the sqaure root of 'n'
  for (int i = 2; i * i <= n; i++) {

  //If 'i' is a factor of 'n'
  if (n % i == 0) {
  while (n % i == 0){
n /= i;
}
ans -= ans / i;
}
}
  if (n > 1){
ans -= ans / n;
}

  return ans;
}

int main() {
  int n = 12;
  cout << eulerTotient(n) << endl;
}

Output:

Time Complexity: The time complexity of the above approach is O(√N) because we are running an O(√N) for loop only.

Space Complexity: The space complexity for the above approach is O(1) because we are using constant auxiliary space.

Also see, Euclid GCD Algorithm

Approach 2:

We can optimize the above approach for Euler’s Totient by efficiently calculating the prime factors of a number. We can use the Sieve of Eratosthenes to efficiently calculate the factors of a number. Instead of updating the temporary result for each prime factor for each number, we find all prime numbers. For each one, update the temporary results of all numbers divisible by that prime number.

#include<bits/stdc++.h>
using namespace std;

void eulerTotient(int n) {
  vector<int> phi(n + 1);
phi[0] = 0;
phi[1] = 1;
  for (int i = 2; i <= n; i++){
phi[i] = i;
}

  for (int i = 2; i <= n; i++) {
  if (phi[i] == i) {
  for (int j = i; j <= n; j += i){
phi[j] -= phi[j] / i;
}
}
}
  cout << phi[n] << endl;
}

int main() {
  int n = 12;
eulerTotient(n);
}

Output:

Time Complexity: The time complexity of the above approach is O(N * log(log(N))) because we are applying a similar approach to the Sieve of Eratosthenes.

Space Complexity: The space complexity for the above approach is O(N) because we are maintaining a ‘phi’ array of size ‘N’.

Approach 3:

There is one interesting property by Gauss:

∑ϕ(d) = N

d|n

Here the sum is over all positive divisors ‘d’ of ‘N’.

Let us say N = 12.

Divisors of N are 1, 2, 3, 4, 6, 12

Hence, ϕ(1) + ϕ(2) + ϕ(3) + ϕ(4) + ϕ(6) + ϕ(12) = 1 + 1 +2 + 2 + 2 + 4 = 12

Using the above property we can also implement the Euler’s Totient function.

#include<bits/stdc++.h>
using namespace std;

void eulerTotient(int n) {
  vector<int> phi(n + 1);

phi[0] = 0;
phi[1] = 1;

  for (int i = 2; i <= n; i++){
phi[i] = i - 1;
}

  for (int i = 2; i <= n; i++){
  for (int j = 2 * i; j <= n; j += i){
phi[j] -= phi[i];
}
}

cout << phi[n] << endl;
}

int main() {
int n = 12;
eulerTotient(n);
}

Output:

Time Complexity: The time complexity for the above approach is O(N * log(N)) because we are running two nested for loops. The outer for loop runs in O(N) time and the inner for loop takes O(log(N)) time.

Space Complexity: The space complexity for the above approach is O(N) because we are maintaining a ‘phi’ array of size ‘N’.

FAQs:

What is Euler’s Totient function?

Euler’s totient function counts the total numbers between 1 to N, which are coprime to ‘N.’ Two numbers are said to be coprime if the G.C.D.(Greatest Common Divisor) of both the numbers is 1.

2.What is the most time-optimized approach to implement Euler’s totient function?

The most time-optimized approach for the Euler’s totient function is O(n * log(log(n))) which we implement using Sieve of Eratosthenes.

Key Takeaways:

In this blog, we have covered the following things:

We first discussed what Euler’s totient function is.
Then we discussed the different implementations for Euler’s totient function.

If you want to learn more about Number Theory and want to practice some questions which require you to take your basic knowledge on Number Theory a notch higher, then you can visit our Guided Path for Number Theory.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass

Land an SDE Role at Google: Master DSA the smart way

by Saurav Prateek, SDE2@Google

19 Sep, 2024

01:30 PM

38+ registered

Become a Data Analyst at MAANG: Learn PowerBI for Data visualization

by Megna Roy, Senior Data Analyst @Amazon

17 Sep, 2024

01:30 PM

281+ registered

Learn Advanced Excel: Ace Data Analytics Interview

by Megna Roy, Data Analyst @ Amazon

15 Sep, 2024

06:30 AM

3858+ registered

Land an SDE Role at Google: Master DSA the smart way

by Saurav Prateek, SDE2@Google

19 Sep, 2024

01:30 PM

38+ registered

Become a Data Analyst at MAANG: Learn PowerBI for Data visualization

by Megna Roy, Senior Data Analyst @Amazon

17 Sep, 2024

01:30 PM

281+ registered

View more events