修改Euler函数 [英] modifying Euler Totient Function

问题描述

要计算整数互质数为N，少的数量小于N，我们可以简单地计算出它的 ETF 。然而，为了calcuate整数互质数为N，但小于数M，其中M＆LT; N，我们怎么可以修改/计算呢？ 我曾尝试code到calcuate的ETF，但不能进行如何修改它，以获得所需的结果。

to calculate the number of integers co-prime to N and less than N we can simply calculate its ETF . However to calcuate the number of integers co-prime to N but less then M where M < N , how can we modify / calculate it ? I have tried the code to calcuate the ETF but can't proceed how to modify it to get the required result.

code：

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

感谢

推荐答案

您需要使用的容斥原理。让我们做一个例子：假设你想计算整数互质到30 = 2 * 3 * 5和小于20量

You need to use the inclusion-exclusion principle. Let's do an example: suppose you want to calculate the amount of integers coprime to 30 = 2 * 3 * 5 and smaller than 20.

首先要注意的事情是，你可以指望那些不互质30和从总相反，这是一个容易得多相减的数字。的2小于20的倍数的数目是20/2 = 10，为3的倍数的数量为20/3 = 6（在发言），和5的倍数的数目是20/5 = 4。

The first thing to note is that you can count the numbers that are not coprime to 30 and subtract them from the total instead, which is a lot easier. The number of multiples of 2 less than 20 is 20/2 = 10, the number of multiples of 3 is 20/3 = 6 (taking the floor), and the number of multiples of 5 is 20/5 = 4.

不过，请注意，我们统计的数字，如6 = 2 * 3不止一次，无论是在2的倍数为3的倍数。考虑到这一点，我们必须减去每一个数字，它是的倍数两个素数的乘积。

However, note that we counted numbers such as 6 = 2 * 3 more than once, both in the multiples of 2 and the multiples of 3. To account for that, we have to subtract every number that is a multiple of the product of two primes.

这，在另一方面，减去这三个素数一度超过必要的倍数号码 - 所以你必须是数添加到末尾。像这样做，交替的迹象，直到你到达的素数的总数除以N.在这个例子中，答案应该是

This, on the other hand, subtracts numbers that are multiples of three of the primes once more than necessary -- so you have to add that count to the end. Do it like this, alternating signs, until you reach the total number of primes that divide N. In the example, the answer would be

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。

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。）

(The numbers we're counting are 1, 7, 11, 13, 17 and 19.)

这篇关于修改Euler函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！