1

要计算与 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; 
 }

谢谢

4

1 回答 1

5

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

首先要注意的是，您可以计算不互质为 30 的数字，然后从总数中减去它们，这要容易得多。2小于20的倍数是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。）

于 2012-10-03T18:33:36.627 回答