algorithm - 修改 Euler Totient 函数

Question

要计算与 N 互质且小于 N 的整数的数量，我们可以简单地计算它的 ETF .然而，要计算与 N 互质但小于 M 的整数数量，其中 M < N，我们如何修改/计算它？我已尝试使用代码来计算 ETF，但无法继续如何修改它以获得所需的结果。

代码:

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; 
 }

谢谢

Answer 1

您需要使用 inclusion-exclusion principle .举个例子:假设你想计算与30 = 2 * 3 * 5互质且小于20的整数个数。

首先要注意的是，您可以将不互质的数字数到 30，然后从总数中减去它们，这样就容易多了。 20以内的2的倍数是20/2=10，3的倍数是20/3=6(发言)，5的倍数是20/5=4。

但是，请注意，我们不止一次计算过 6 = 2 * 3 之类的数字，包括 2 的倍数和 3 的倍数。为了说明这一点，我们必须减去每个数字的倍数两个素数的乘积。

另一方面，这会多次减去三个素数的倍数——因此您必须将该计数添加到末尾。这样做，交替符号，直到达到整除 N 的素数总数。在示例中，答案将是

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.

(我们数的数字是 1、7、11、13、17 和 19。)