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 と互いに素でない数を数えて、代わりに合計から差し引くことができるということです。これははるかに簡単です。20 未満の 2 の倍数は 20/2 = 10、3 の倍数は 20/3 = 6 (議席を取る)、5 の倍数は 20/5 = 4 です。

ただし、2 の倍数と 3 の倍数の両方で、6 = 2 * 3 などの数を 2 回以上数えたことに注意してください。これを考慮するには、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 に答える