math/eulerphi.cpp

View this file on GitHub
Last update: 2021-02-19 21:44:59+09:00

Code

int eulerphi(int x){
    int phi = x, xx = x;
    for (int i = 2; i * i <= x; ++i) {
        if (xx % i == 0) {
            phi -= phi / i;
            while(xx % i == 0) xx /= i;
        }
    }
    if(xx > 1) phi -= phi/xx;
    return phi;
}

#line 1 "math/eulerphi.cpp"
int eulerphi(int x){
    int phi = x, xx = x;
    for (int i = 2; i * i <= x; ++i) {
        if (xx % i == 0) {
            phi -= phi / i;
            while(xx % i == 0) xx /= i;
        }
    }
    if(xx > 1) phi -= phi/xx;
    return phi;
}