algorithm - modifying Euler Totient Function

Question

to calculate the number of integers co-prime to N and less than N we can simply calculate its ETF . However to calcuate the number of integers co-prime to N but less then M where M < N , how can we modify / calculate it ? I have tried the code to calcuate the ETF but can't proceed how to modify it to get the required result.

Code:

int etf(int n) 
{ 
   int result = n; 
   int i;
   for(i=2;i*i <= n;i++) 
   { 

        if (n % i == 0) result -= result / i; 
        while (n % i == 0) n /= i;
   } 
   if (n > 1) result -= result / n; 
   return result; 
 }

Thanks

Answer 1

You need to use the inclusion-exclusion principle. Let's do an example: suppose you want to calculate the amount of integers coprime to 30 = 2 * 3 * 5 and smaller than 20.

The first thing to note is that you can count the numbers that are not coprime to 30 and subtract them from the total instead, which is a lot easier. The number of multiples of 2 less than 20 is 20/2 = 10, the number of multiples of 3 is 20/3 = 6 (taking the floor), and the number of multiples of 5 is 20/5 = 4.

However, note that we counted numbers such as 6 = 2 * 3 more than once, both in the multiples of 2 and the multiples of 3. To account for that, we have to subtract every number that is a multiple of the product of two primes.

This, on the other hand, subtracts numbers that are multiples of three of the primes once more than necessary -- so you have to add that count to the end. Do it like this, alternating signs, until you reach the total number of primes that divide N. In the example, the answer would be

20/1 - 20/2 - 20/3 - 20/5 + 20/2*3 + 20/3*5 + 20/2*5 - 20/2*3*5 = 20 - 10 - 6 - 4 + 3 + 1 + 2 - 0 = 6.

(The numbers we're counting are 1, 7, 11, 13, 17 and 19.)