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 .)

Definition[edit]

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

Properties[edit]

  • 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 .

Implementation[edit]

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;

        res=i;

        /* Check for divisibility by every prime number below the square root. */
        /* Start with 2. */
        if (i%2==0)
        {
		res-=res/2;
		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)
		{
			res-=res/j;
			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; 
}