Euler's Phi function

From Algorithmist
Jump to navigation Jump to search

Euler's Phi function, also known as the totient function, is a function that, for a given positive integer , calculates the number of positive integers smaller than or equal to that are relatively prime to . (Note that except when , only integers strictly smaller than are counted, because .)


, where denotes the greatest common divisor of i and N.


  • for prime, because all numbers smaller than are relatively prime to .
  • is even for all , because if is relatively prime to , so is , and they are distinct.
  • It is a multiplicative function in the number-theoretic sense: whenever .
  • , because among the integers from to , the integers not relatively prime to are precisely those divisible by , and there are of them. From this and multiplicativity, we can deduce a formula for in general:
  • Let be the prime factorisation of . That is, the s are distinct primes and each is a positive integer. Then .


Although not the fastest, the following C implementation will work:

num_t totient (num_t i)
	num_t res; /* Result */
	num_t j;

	if (i==1) return 1;


        /* Check for divisibility by every prime number below the square root. */
        /* Start with 2. */
        if (i%2==0)
		do i/=2; while (i%2==0) ;

        /* Since this doesn't use a list of primes, check every odd number. Ideally, skip past composite numbers.*/
	for (j=3; j*j<=i; j+=2)
		if (i%j==0)
			do i/=j; while (i%j==0) ;

        /* If i>1, then it's the last factor at this point. */
	if (i>1) res-=res/i;

        /* Return the result. */
	return res;