要计算互素为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; }
谢谢
您需要使用包含- 排除原则。让我们做一个例子：假设您要计算coprime为30 = 2 * 3 * 5且小于20的整数的数量。
首先要注意的是，您可以算出不是互质数为30的数字，然后从总数中减去它们，这很容易。小于20的2的倍数是20/2 = 10，3的倍数是20/3 = 6（取下限），而5的倍数是20/5 = 4。
但是，请注意，我们不仅对2 = 3的倍数而且对6 = 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。）
