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 回答