Algotree > Algorithms > Numeric > Euler's Totient Function

Euler's Totient Function

Euler’s Totient function is also known as the Phi function.
It computes the count ( also referred as totatives ) of positive integers up to N that are coprime ( relatively prime ) to N.
- Coprime ( Relatively prime ) : Two integers A and B are coprime if 1 is the greatest common divisor ( GCD ) of A and B.
Eulter’s Totient Function is represented by a Greek letter phi Φ.
It is evident that the totatives of a prime number Φ ( P ) = P - 1

Example of totatives of a given number

Φ(20) = 8. i.e Numbers 1, 3, 7, 9, 11, 13, 17 and 19 are relatively prime to 20.
Φ(15) = 8. i.e Numbers 1, 2, 4, 7, 8, 11, 13 and 14 are relatively prime to 15.
Φ(12) = 4. i.e Numbers 1, 5, 7 and 11 are relatively prime to 12.
Φ(17) = 16. i.e Numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 and 16.
Φ(9) = 6. i.e Numbers 1, 2, 4, 5, 7 and 8 are relatively prime to 9.

Euler_Totient

Euler’s totient function implementation

def EulersTotient ( N ) :

    # Setting initial number of totatives to N
    ans = N
    i = 2

    while (i*i <= N) :

        if (N % i == 0) :
            ans = (ans - int(ans/i))

        while (N % i == 0) :
            N = N/i

        i += 1

    if (N > 1) : 
        ans = ans - int(ans/N)

    return str(int(ans))

def main():

    print("Φ(15) = " + EulersTotient(15))
    print("Φ(12) = " + EulersTotient(12))
    print("Φ(17) = " + EulersTotient(17))
    print("Φ(9) = " + EulersTotient(9))
    print("Φ(98) = " + EulersTotient(98))
    print("Φ(100) = " + EulersTotient(100))

if __name__ == "__main__" :
   main()

Output of Euler’s totient function implemented in Python3

Φ(15) = 8
Φ(12) = 4
Φ(17) = 16
Φ(9) = 6
Φ(98) = 42
Φ(100) = 40

#include<iostream>

using namespace std;

int EulersTotient (int N) { 

    // Setting initial number of totatives to N
    int ans = N;
    for (int i=2; i*i <= N; i++) {
        if (N % i == 0) { 
            ans = ans - ans/i;
        }
        while (N % i == 0)
            N = N/i;
    }

    if (N > 1)
        ans = ans - ans/N;

    return ans;
}

int main() {

    cout << "Φ(15) = " << EulersTotient(15) << endl;
    cout << "Φ(12) = " << EulersTotient(12) << endl;
    cout << "Φ(17) = " << EulersTotient(17) << endl;
    cout << "Φ(9) = " << EulersTotient(9) << endl;
    cout << "Φ(98) = " << EulersTotient(98) << endl;
    cout << "Φ(100) = " << EulersTotient(100) << endl;
    return 0;
}

Output of Euler’s totient function implemented in C++

Φ(15) = 8
Φ(12) = 4
Φ(17) = 16
Φ(9) = 6
Φ(98) = 42
Φ(100) = 40

class Euler {

    int EulersTotient (int N) { 
    
        // Setting initial number of totatives to N
        int ans = N;
        for (int i=2; i*i <= N; i++) {
            if (N % i == 0) { 
                ans = ans - ans/i;
            }
            while (N % i == 0)
                N = N/i;
        }

        if (N > 1)
            ans = ans - ans/N;
    
        return ans;
    }   
    
    public static void main (String args[]) {

        Euler obj = new Euler();
    
        System.out.println("Φ(15) = " + obj.EulersTotient(15));
        System.out.println("Φ(12) = " + obj.EulersTotient(12));
        System.out.println("Φ(17) = " + obj.EulersTotient(17));
        System.out.println("Φ(9) = " + obj.EulersTotient(9));
        System.out.println("Φ(98) = " + obj.EulersTotient(98));
        System.out.println("Φ(100) = " + obj.EulersTotient(100));
    }   
}

Output of Euler’s totient function implemented in Java

Φ(15) = 8
Φ(12) = 4
Φ(17) = 16
Φ(9) = 6
Φ(98) = 42
Φ(100) = 40