オイラーのピー関数の実装の背後にある

Question

私はトップコーダーでオイラーのphi関数の実装を発見しました。コードは次のとおりです。

int fi(int n) {   
    int result = n;   
    for(int 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;   
} 

この実装の背後にある正確な理論を知りたいと思います。私が理解しているのは、nを分ける整数を得た場合、結果からresult/iを減算しているということです（私には分かりません）。分母になるまで、コードはnで分けられます。私が理解できなかったのは、コードの最後の部分です。

if(n > 1) result -= result/n; 

nが、この段階では1よりも大きいnは素数になる場合私が知っていることです。私が知りたいのは、もし私が今までこのコードから理解していることが正しいとすれば、このコードの背後にある正確な理論です。

Answer 1

ルックアップオイラーのtotient関数。アルゴリズムは忠実に計算

phi(p1^m1*...*pk^mk) = (p1-1)*p1^(m1-1)*...*(pk-1)*pk^(mk-1) 

その後数nが素数のべき乗の積に分解される場合

、。

可逆的な残りのクラスmod nの数です。 gcd(a,n)=1次いで

a^b == a^(b mod phi(n)) mod n 

---

反復は昇順に入力nの素因数を発見した場合、それは、フェルマーの拡張少し定理ための指数です。 pが素因数として見つかる場合、result = k*p^mここで、mは、入力のpの多重度でもあります。操作result -= result/pは結果

result = k*p^m - k*p^(m-1) = k*(p-1)*p^(m-1). 

があり、反復が最大の素因数がm=1多重度を持っている場合に発生します、とトーティエント値にこの係数は1減少発生した後、あなたは、n>1正しいです。