Теория за реализацией функции функции Филера

Question

Я нашел реализацию phi-функции эйлера на topcoder. Код приведен ниже:

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 на i, пока он не делится. То, что я не понял, является последней частью кода.

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

Я знаю, что если n на этом этапе больше 1, то n будет простым числом. Я хочу знать, если то, что я понимаю из этого кода, является правильным и точной теорией этого кода.

Answer 1

Ищите Функция поиска Эйлера.

Если число n разлагается в произведение силы простых чисел, а затем

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

, который точно вычисляет алгоритм.

Это число оставшихся классов 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). 

И вы правы, n>1 после итерации будет происходить, когда наибольший простой фактор имеет кратность m=1, и в значении totient этот фактор происходит снижение на 1.