Professor Java
Your Ad Here

Euler's Totient Function Calculator


Number:

φ(n) (Totient of n):


Euler's Totient Theorem

 public static int totient(int num){ //euler's totient function calculator. returns totient
    int count=0;
    for(int a=1;a<num;a++){ //definition of totient: the amount of numbers less than num coprime to it
      if(GCD(num,a)==1){ //coprime
        count++;
      }
    }
    return(count);
 }
public static int GCD(int a, int b){ //faster euclidean algorithm-see GCD for explanation
    int temp;
    if(a<b){
      temp=a;
      a=b;
      b=temp;
    }
    if(a%b==0){
      return(b);
    }
    return(GCD(a%b,b));
  }

The Euler Totient function, denoted phi(n) or totient(n), is the amount of numbers less than n relatively prime, or coprime to it. It has many uses, particularly Euler's Totient Theorem that for all a coprime to n. There is also other ways to calculate totient(n), but they were slower than my implementation. It works by looping through 2->num, because 1 is always relatively prime to all numbers, we account for that and start at 2. We check if GCD(num,i) is 1, which shows they are relatively prime. The Euclidean algorithm provides a quick recursive way to do this (see GCD page), and I sped it up considerably by implementing the fast Euclidean algorithm. The Javascript totient calculator implementation is above, using the exact same Java algorithm. 

website-hit-counters.com
Provided by website-hit-counters.com site.
Your Ad Here