# Euler's Totient Function

Euler’s Totient Function also known as Phi Function 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/relatively prime/mutually prime 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’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
``````