Tutorialspoint.dev

Euler’s Totient function for all numbers smaller than or equal to n

Euler’s Totient function Φ(n) for an input n is 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.

For example, Φ(4) = 2, Φ(3) = 2 and Φ(5) = 4. There are 2 numbers smaller or equal to 4 that are relatively prime to 4, 2 numbers smaller or equal to 3 that are relatively prime to 3. And 4 numbers smaller than or equal to 5 that are relatively prime to 5.

We have discussed different methods for computation of Φ(n) in previous post.

How to compute Φ for all numbers smaller than or equal to n?
Example:

Input: n = 5
Output: Totient of 1 is 1
        Totient of 2 is 1
        Totient of 3 is 2
        Totient of 4 is 2
        Totient of 5 is 4 

We strongly recommend you to minimize your browser and try this yourself first.



A Simple Solution is to call Φ(i) for i = 1 to n.

An Efficient Solution is to use idea similar to Sieve of Eratosthenes to precompute all values/. The method is based on below product formula.

eulersproduct

The formula basically says that the value of Φ(n) is equal to n multiplied by 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.

Below is complete algorithm:

1) Create an array phi[1..n] to store Φ values of all numbers 
   from 1 to n.  

2) Initialize all values such that phi[i] stores i.  This
   initialization serves two purposes.
   a) To check if phi[i] is already evaluated or not. Note that
      the maximum possible phi value of a number i is i-1.
   b) To initialize phi[i] as i is a multiple in above product
      formula. 

3) Run a loop for p = 2 to n
    a) If phi[p] is p, means p is not evaluated yet and p is a 
       prime number (slimier to Sieve), otherwise phi[p] must 
       have been updated in step 3.b
    b) Traverse through all multiples of p and update all 
       multiples of p by multiplying with (1-1/p).

4) Run a loop from i = 1 to n and print all Ph[i] values. 

Below is the implementation of above algorithm.

C++

// C++ program to compute Totient function for
// all numbers smaller than or equal to n.
#include<iostream>
using namespace std;
  
// Computes and prints totien of all numbers
// smaller than or equal to n.
void computeTotient(int n)
{
    // Create and initialize an array to store
    // phi or totient values
    long long phi[n+1];
    for (int i=1; i<=n; i++)
        phi[i] = i; // indicates not evaluated yet
                    // and initializes for product
                    // formula.
  
    // Compute other Phi values
    for (int p=2; p<=n; p++)
    {
        // If phi[p] is not computed already,
        // then number p is prime
        if (phi[p] == p)
        {
            // Phi of a prime number p is
            // always equal to p-1.
            phi[p] = p-1;
  
            // Update phi values of all
            // multiples of p
            for (int i = 2*p; i<=n; i += p)
            {
               // Add contribution of p to its
               // multiple i by multiplying with
               // (1 - 1/p)
               phi[i] = (phi[i]/p) * (p-1);
            }
        }
    }
  
    // Print precomputed phi values
    for (int i=1; i<=n; i++)
      cout << "Totient of " << i << " is "
           << phi[i] << endl;
}
  
// Driver program to test above function
int main()
{
    int n = 12;
    computeTotient(n);
    return 0;
}

Java

// Java program to compute Totient 
// function for all numbers smaller
// than or equal to n.
import java.util.*;
  
class GFG {
      
// Computes and prints totient of all numbers
// smaller than or equal to n.
static void computeTotient(int n) {
      
    // Create and initialize an array to store
    // phi or totient values
    long phi[] = new long[n + 1];
    for (int i = 1; i <= n; i++)
    phi[i] = i; // indicates not evaluated yet
                // and initializes for product
                // formula.
  
    // Compute other Phi values
    for (int p = 2; p <= n; p++) {
          
    // If phi[p] is not computed already,
    // then number p is prime
    if (phi[p] == p) {
          
        // Phi of a prime number p is
        // always equal to p-1.
        phi[p] = p - 1;
  
        // Update phi values of all
        // multiples of p
        for (int i = 2 * p; i <= n; i += p) {
              
        // Add contribution of p to its
        // multiple i by multiplying with
        // (1 - 1/p)
        phi[i] = (phi[i] / p) * (p - 1);
        }
    }
    }
  
    // Print precomputed phi values
    for (int i = 1; i <= n; i++)
    System.out.println("Totient of " + i +
                         " is " + phi[i]);
}
  
// Driver code
public static void main(String[] args) {
      
    int n = 12;
    computeTotient(n);
}
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python program to compute
# Totient function for
# all numbers smaller than
# or equal to n.
  
# Computes and prints
# totient of all numbers
# smaller than or equal to n.
def computeTotient(n):
  
    # Create and initialize
    # an array to store
    # phi or totient values
    phi=[]
    for i in range(n + 2):
        phi.append(0)
  
    for i in range(1, n+1):
  
        phi[i] = i # indicates not evaluated yet
                    # and initializes for product
                    # formula.
   
    # Compute other Phi values
    for p in range(2,n+1):
      
        # If phi[p] is not computed already,
        # then number p is prime
        if (phi[p] == p):
          
            # Phi of a prime number p is
            # always equal to p-1.
            phi[p] = p-1
   
            # Update phi values of all
            # multiples of p
            for i in range(2*p,n+1,p):
              
                # Add contribution of p to its
                # multiple i by multiplying with
                # (1 - 1/p)
                phi[i] = (phi[i]//p) * (p-1)
      
   
    # Print precomputed phi values
    for i in range(1,n+1):
        print("Totient of ", i ," is ",
           phi[i])
  
# Driver code
  
n = 12
computeTotient(n)
  
# This code is contributed
# by Anant Agarwal

C#

// C# program to check if given two
// strings are at distance one.
using System;
  
class GFG
{
      
// Computes and prints totient of all
// numbers smaller than or equal to n
static void computeTotient(int n) 
{
      
    // Create and initialize an array to 
    // store phi or totient values
    long []phi = new long[n + 1];
    for (int i = 1; i <= n; i++)
      
    // indicates not evaluated yet
    // and initializes for product
    // formula.
    phi[i] = i; 
      
    // Compute other Phi values
    for (int p = 2; p <= n; p++) 
    {
          
    // If phi[p] is not computed already,
    // then number p is prime
    if (phi[p] == p) 
    {
          
        // Phi of a prime number p is
        // always equal to p-1.
        phi[p] = p - 1;
  
        // Update phi values of all
        // multiples of p
        for (int i = 2 * p; i <= n; i += p) 
        {
              
        // Add contribution of p to its
        // multiple i by multiplying with
        // (1 - 1/p)
        phi[i] = (phi[i] / p) * (p - 1);
          
        }
    }
    }
  
    // Print precomputed phi values
    for (int i = 1; i <= n; i++)
    Console.WriteLine("Totient of " + i +" is " + phi[i]);
}
  
// Driver code
public static void Main()
{
      
    int n = 12;
    computeTotient(n);
}
}
  
// This code is contributed by Sam007.

PHP

<?php
// PHP program to compute Totient
// function for all numbers smaller 
// than or equal to n.
  
// Computes and prints totient
// of all numbers smaller than
// or equal to n.
function computeTotient($n)
{
      
    // Create and initialize 
    // an array to store
    // phi or totient values
    for($i = 1; $i <= $n; $i++)
      
        // indicates not evaluated yet
        // and initializes for product
        // formula.
        $phi[$i] = $i
  
    // Compute other Phi values
    for($p = 2; $p <= $n; $p++)
    {
          
        // If phi[p] is not computed already,
        // then number p is prime
        if ($phi[$p] == $p)
        {
              
            // Phi of a prime number p is
            // always equal to p-1.
            $phi[$p] = $p - 1;
  
            // Update phi values of all
            // multiples of p
            for($i = 2 * $p; $i <= $n; $i += $p)
            {
                  
                // Add contribution of p to its
                // multiple i by multiplying with
                // (1 - 1/$p)
                $phi[$i] = ($phi[$i] / $p) * ($p - 1);
            }
        }
    }
  
    // Print precomputed phi values
    for($i = 1; $i <= $n; $i++)
    echo "Totient of " , $i , " is ",
        $phi[$i] ," ";
}
  
    // Driver Code
    $n = 12;
    computeTotient($n);
  
// This code is contributed by ajit
?>


Output:

Totient of 1 is 1
Totient of 2 is 1
Totient of 3 is 2
Totient of 4 is 2
Totient of 5 is 4
Totient of 6 is 2
Totient of 7 is 6
Totient of 8 is 4
Totient of 9 is 6
Totient of 10 is 4
Totient of 11 is 10
Totient of 12 is 4

The same solution can be used when we have large number queries for computing totient function.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter