math/eulers-phi-function.hpp

• View this file on GitHub
• Last update: 2023-04-10 01:04:21+09:00
• Include: #include "math/eulers-phi-function.hpp"

Verified with

• verify/AOJ-NTL_1_D.test.cpp

Code

template <typename T>
T eulersPhiFunction(T n){
    T res = n;
    for(T i = 2; i * i <= n; ++i){
        if(n % i == 0){
            res -= res / i;
            while(n % i == 0) n /= i;
        }
    }

    if(n > 1) res -= res / n;
    return res;
}

#line 1 "math/eulers-phi-function.hpp"
template <typename T>
T eulersPhiFunction(T n){
    T res = n;
    for(T i = 2; i * i <= n; ++i){
        if(n % i == 0){
            res -= res / i;
            while(n % i == 0) n /= i;
        }
    }

    if(n > 1) res -= res / n;
    return res;
}

Back to top page