修改 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

您需要使用包含-排除原则。让我们举个例子：假设您要计算互质为 30 = 2 * 3 * 5 且小于 20 的整数的数量。

首先要注意的是，您可以将不是互质数的数字计算为 30，然后从总数中减去它们，这会容易得多。2小于20的倍数是20/2=10，3的倍数是20/3=6（下），5的倍数是20/5=4。

但是，请注意，我们多次计算了诸如 6 = 2 * 3 之类的数字，包括 2 的倍数和 3 的倍数。为了解决这个问题，我们必须减去每个是 2 的乘积倍数的数字素数。

另一方面，这会多次减去三个素数的倍数——因此您必须将该计数添加到末尾。这样做，交替符号，直到达到整除 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。）